Magic numbers

Magic numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Magic numbers are polydivisible numbers in base 10. A polydivisible number is a number where the first n digits are evenly divisible by n.

E.G. The number 1868587 is a magic number (is polydivisible in base 10.)

      1 ÷ 1 = 1
     18 ÷ 2 = 9
    186 ÷ 3 = 62
   1868 ÷ 4 = 467
  18685 ÷ 5 = 3737
 186858 ÷ 6 = 31143
1868587 ÷ 7 = 266941

There is a finite number of magic numbers.

Task

• Write a routine (subroutine, function, procedure, generator, whatever it may be called in your language) to find magic numbers.
• Use that routine to find and display how many magic numbers exist.
• Use that routine to find and display the largest possible magic number.
• Count and display how many magic numbers have 1 digit, 2 digits, 3 digits, ... for all magic numbers.
• Find and display all of the magic numbers that are minimally pandigital in 1 through 9. (Contains each digit but only once.)
• Find and display all of the magic numbers that are minimally pandigital in 0 through 9.

Zero (0) may or may not be included as a magic number. For this task, include zero.

See also

• Wikipedia: Polydivisible numbers
• OEIS:A144688 - "Magic" numbers
• OEIS:A143671 - Count of "Magic" numbers with n digits

C++

#include <array>
#include <iostream>
#include <numeric>
#include <vector>

#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::uint128_t;

class magic_number_generator {
public:
    magic_number_generator() : magic_(10) {
        std::iota(magic_.begin(), magic_.end(), 0);
    }
    bool next(uint128_t& n);

public:
    std::vector<uint128_t> magic_;
    size_t index_ = 0;
    int digits_ = 2;
};

bool magic_number_generator::next(uint128_t& n) {
    if (index_ == magic_.size()) {
        std::vector<uint128_t> magic;
        for (uint128_t m : magic_) {
            if (m == 0)
                continue;
            uint128_t n = 10 * m;
            for (int d = 0; d < 10; ++d, ++n) {
                if (n % digits_ == 0)
                    magic.push_back(n);
            }
        }
        index_ = 0;
        ++digits_;
        magic_ = std::move(magic);
    }
    if (magic_.empty())
        return false;
    n = magic_[index_++];
    return true;
}

std::array<int, 10> get_digits(uint128_t n) {
    std::array<int, 10> result = {};
    for (; n > 0; n /= 10)
        ++result[static_cast<int>(n % 10)];
    return result;
}

int main() {
    int count = 0, dcount = 0;
    uint128_t magic = 0, p = 10;
    std::vector<int> digit_count;

    std::array<int, 10> digits0 = {}, digits1 = {};
    std::fill(digits0.begin(), digits0.end(), 1);
    std::fill(digits1.begin() + 1, digits1.end(), 1);
    std::vector<uint128_t> pandigital0, pandigital1;

    for (magic_number_generator gen; gen.next(magic);) {
        if (magic >= p) {
            p *= 10;
            digit_count.push_back(dcount);
            dcount = 0;
        }
        auto digits = get_digits(magic);
        if (digits == digits0)
            pandigital0.push_back(magic);
        else if (digits == digits1)
            pandigital1.push_back(magic);
        ++count;
        ++dcount;
    }
    digit_count.push_back(dcount);

    std::cout << "There are " << count << " magic numbers.\n\n";
    std::cout << "The largest magic number is " << magic << ".\n\n";

    std::cout << "Magic number count by digits:\n";
    for (int i = 0; i < digit_count.size(); ++i)
        std::cout << i + 1 << '\t' << digit_count[i] << '\n';

    std::cout << "\nMagic numbers that are minimally pandigital in 1-9:\n";
    for (auto m : pandigital1)
        std::cout << m << '\n';

    std::cout << "\nMagic numbers that are minimally pandigital in 0-9:\n";
    for (auto m : pandigital0)
        std::cout << m << '\n';
}

Output:

There are 20457 magic numbers.

The largest magic number is 3608528850368400786036725.

Magic number count by digits:
1	10
2	45
3	150
4	375
5	750
6	1200
7	1713
8	2227
9	2492
10	2492
11	2225
12	2041
13	1575
14	1132
15	770
16	571
17	335
18	180
19	90
20	44
21	18
22	12
23	6
24	3
25	1

Magic numbers that are minimally pandigital in 1-9:
381654729

Magic numbers that are minimally pandigital in 0-9:
3816547290

Phix

Using strings

with javascript_semantics
function polydivisible()
    sequence res = {}, prev = {""}, next = {}
    integer digits = 1
    while length(prev) do
        for np in prev do
            for d='0'+(digits=1) to '9' do
                string n = np&d
                integer rem = 0
                for nd in n do
                    rem = remainder(rem*10+nd-'0',digits)
                end for
                if rem=0 then
                    next = append(next,n)
                end if
            end for
        end for
        if length(next) then
            res = append(res,next)
        end if
        prev = next
        next = {}
        digits += 1
    end while
    res[1] &= {"0"}
    return res
end function

sequence r = polydivisible(),
        rc = apply(r,length)
string fmt = """
There are %,d magic numbers in total.

The largest is %s.

There are:
"""
printf(1,fmt,{sum(rc),r[$][$]})
for i,c in rc do
    printf(1,"%,5d with %2d digit%s\n",{c,i,iff(i=1?"":"s")})
end for
function pandigital(string s,p) return sort(s)=p end function
function evenonly(string s) return sum(apply(s,odd))=0 end function
function filter_even(sequence ri) return filter(ri,evenonly) end function
function palindromic(string s) return s=reverse(s) end function
function filter_pal(sequence ri) return filter(ri,palindromic) end function
string p1 = join(filter(r[9],pandigital,"123456789"),"\n"),
       p0 = join(filter(r[10],pandigital,"0123456789"),"\n"),
       evenpd = trim_tail(apply(r,filter_even),{{}})[$][$],
       pallypd = trim_tail(apply(r,filter_pal),{{}})[$][$]
fmt = """%s
All magic numbers that are pan-digital in 1 through 9 with no repeats:
 %s

All magic numbers that are pan-digital in 0 through 9 with no repeats:
 %s

The longest polydivisible number that only uses even digits is:
 %s

The longest palindromic polydivisible number is:
 %s
"""
printf(1,fmt,{"\n",p1,p0,evenpd,pallypd})

Output:

There are 20,457 magic numbers in total.

The largest is 3608528850368400786036725.

There are:
   10 with  1 digit
   45 with  2 digits
  150 with  3 digits
  375 with  4 digits
  750 with  5 digits
1,200 with  6 digits
1,713 with  7 digits
2,227 with  8 digits
2,492 with  9 digits
2,492 with 10 digits
2,225 with 11 digits
2,041 with 12 digits
1,575 with 13 digits
1,132 with 14 digits
  770 with 15 digits
  571 with 16 digits
  335 with 17 digits
  180 with 18 digits
   90 with 19 digits
   44 with 20 digits
   18 with 21 digits
   12 with 22 digits
    6 with 23 digits
    3 with 24 digits
    1 with 25 digits

All magic numbers that are pan-digital in 1 through 9 with no repeats:
 381654729

All magic numbers that are pan-digital in 0 through 9 with no repeats:
 3816547290

The longest polydivisible number that only uses even digits is:
 48000688208466084040

The longest palindromic polydivisible number is:
 30000600003

Raku

my \Δ = $ = 1;
my @magic = flat 0, [1..9], {last if .not; ++Δ; [(.flat X~ 0..9).grep: * %% Δ]}…*;

put "There are {@magic.eager.elems} magic numbers in total.";
put "\nThe largest is {@magic.tail}.";
put "\nThere are:";
put "{(+.value).fmt: "%4d"} with {.key.fmt: "%2d"} digit{1 == +.key ?? '' !! 's'}"
    for sort @magic.classify: {.chars};
{
    my $pan-digital = ($_..9).join.comb.Bag;
    put "\nAll magic numbers that are pan-digital in $_ through 9 with no repeats: " ~
    @magic.grep( { .comb.Bag eqv $pan-digital } );
} for 1, 0;

Output:

There are 20457 magic numbers in total.

The largest is 3608528850368400786036725.

There are:
  10 with  1 digit
  45 with  2 digits
 150 with  3 digits
 375 with  4 digits
 750 with  5 digits
1200 with  6 digits
1713 with  7 digits
2227 with  8 digits
2492 with  9 digits
2492 with 10 digits
2225 with 11 digits
2041 with 12 digits
1575 with 13 digits
1132 with 14 digits
 770 with 15 digits
 571 with 16 digits
 335 with 17 digits
 180 with 18 digits
  90 with 19 digits
  44 with 20 digits
  18 with 21 digits
  12 with 22 digits
   6 with 23 digits
   3 with 24 digits
   1 with 25 digits

All magic numbers that are pan-digital in 1 through 9 with no repeats: 381654729

All magic numbers that are pan-digital in 0 through 9 with no repeats: 3816547290

Wren

Library: Wren-big

Library: Wren-fmt

This is based on the Python code in the Wikipedia article.

import "./big" for BigInt
import "./fmt" for Fmt

var polydivisible = Fn.new {
    var numbers = []
    var previous = (1..9).toList
    var new = []
    var digits = 2
    while (previous.count > 0) {
        numbers.add(previous)
        for (n in previous) {
            for (j in 0..9) {
                var number = BigInt.ten * n + j
                if (number % digits == 0) new.add(number)
            }
        }
        previous = new
        new = []
        digits = digits + 1
    }
    return numbers
}

var numbers = polydivisible.call()
numbers[0].add(BigInt.zero) // include zero
var total = numbers.reduce(0) { |acc, number| acc + number.count }
Fmt.print("There are $,d magic numbers in total.", total)

var largest = numbers[-1][-1]
Fmt.print("\nThe largest is $,i.", largest)

System.print("\nThere are:")
for (i in 0...numbers.count) {
    Fmt.print("$,5d with $2d digit$s", numbers[i].count, i+1, (i == 0) ? "" : "s")
}

var pd19 = []
for (n in numbers[8]) {
    var s = n.toString
    var pandigital = true
    for (i in 1..9) {
        if (!s.contains(i.toString)) {
            pandigital = false
            break
        }
    }
    if (pandigital) pd19.add(n)
}
System.print("\nAll magic numbers that are pan-digital in 1 through 9 with no repeats: ")
Fmt.print("$,i", pd19)

var pd09 = []
for (n in numbers[9]) {
    var s = n.toString
    var pandigital = true
    for (i in 0..9) {
        if (!s.contains(i.toString)) {
            pandigital = false
            break
        }
    }
    if (pandigital) pd09.add(n)
}
System.print("\nAll magic numbers that are pan-digital in 0 through 9 with no repeats: ")
Fmt.print("$,i", pd09)

Output:

There are 20,457 magic numbers in total.

The largest is 3,608,528,850,368,400,786,036,725.

There are:
   10 with  1 digit 
   45 with  2 digits
  150 with  3 digits
  375 with  4 digits
  750 with  5 digits
1,200 with  6 digits
1,713 with  7 digits
2,227 with  8 digits
2,492 with  9 digits
2,492 with 10 digits
2,225 with 11 digits
2,041 with 12 digits
1,575 with 13 digits
1,132 with 14 digits
  770 with 15 digits
  571 with 16 digits
  335 with 17 digits
  180 with 18 digits
   90 with 19 digits
   44 with 20 digits
   18 with 21 digits
   12 with 22 digits
    6 with 23 digits
    3 with 24 digits
    1 with 25 digits

All magic numbers that are pan-digital in 1 through 9 with no repeats: 
381,654,729

All magic numbers that are pan-digital in 0 through 9 with no repeats: 
3,816,547,290