Magic numbers: Difference between revisions
Content added Content deleted
(→Python: a first quick draft) |
m (→Python: some code cleanup) |
||
Line 473: | Line 473: | ||
def magic_numbers(base): |
def magic_numbers(base): |
||
hist = [] |
|||
n = l = i = 0 |
n = l = i = 0 |
||
while True: |
while True: |
||
l += 1 |
l += 1 |
||
for digit in range(-n % l, base, l) |
hist.extend((n + digit, l) for digit in range(-n % l, base, l)) |
||
all.append((n + digit, l)) |
|||
i += 1 |
i += 1 |
||
if i == len( |
if i == len(hist): |
||
return |
return hist |
||
n, l = |
n, l = hist[i] |
||
n *= base |
n *= base |
||
Line 488: | Line 487: | ||
print("found", len(mn), "magic numbers") |
print("found", len(mn), "magic numbers") |
||
print("the largest one is", mn[-1][0]) |
print("the largest one is", mn[-1][0]) |
||
print("count by digits:") |
print("count by number of digits:") |
||
print(*(f"{l}:{sum(1 for _ in g)}" for l, g in groupby(l for _, l in mn))) |
print(*(f"{l}:{sum(1 for _ in g)}" for l, g in groupby(l for _, l in mn))) |
||
⚫ | |||
mn = tuple(str(m) for m, l in mn if 8 < l < 11) |
|||
⚫ | |||
print("minimally pandigital in 1..9:", 0) |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
found 20457 magic numbers |
found 20457 magic numbers |
||
the largest one is 3608528850368400786036725 |
the largest one is 3608528850368400786036725 |
||
count by digits: |
count by number of 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 |
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 |
||
minimally pandigital in 1..9: |
minimally pandigital in 1..9: 381654729 |
||
⚫ | |||
381654729 |
|||
⚫ | |||
3816547290 |
|||
</pre> |
</pre> |
||
Revision as of 23:08, 10 February 2023
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 an m digit number where the first n digits are evenly divisible by n for all n from 1 to m.
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
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 = {1,1,1,1,1,1,1,1,1,1};
std::array<int, 10> digits1 = {0,1,1,1,1,1,1,1,1,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
F#
// Magic numbers. Nigel Galloway: February 10., 2023
let digs=[|0..10|]|>Array.map(System.UInt128.CreateChecked)
let fN n g=n|>List.collect(fun n->let n=n*digs[10] in [for g in digs[0..9]->n+g]|>List.filter(fun n->n%g=digs[0]))
let fG (n:int []) g=let rec fN g=if g<digs[10] then n[int g]<-n[int g]-1 else n[int(g%digs[10])]<-n[int(g%digs[10])]-1; fN (g/digs[10])
fN g; Array.forall ((=)0) n
let magic=Array.unfold(fun(n,g)->match n with []->None |n->let n=fN n g in Some(n,(n,g+digs[1])))([digs[1]..digs[9]],digs[2])
magic|>Array.iteri(fun n g->printfn "There are %d magic numbers of length %d" (List.length g) (n+2))
printfn $"Largest magic number is %A{magic.[magic.Length-2]|>List.max}"
let fG=fG [|0;1;1;1;1;1;1;1;1;1|] in printf "Minimally pan-digital(1..9) magic numbers are: "; magic[7]|>List.filter fG|>List.iter(printf "%A ");printfn ""
let fG=fG [|1;1;1;1;1;1;1;1;1;1|] in printf "Minimally pan-digital(0..9) magic numbers are: "; magic[8]|>List.filter fG|>List.iter(printf "%A ");printfn ""
- Output:
There are 45 magic numbers of length 2 There are 150 magic numbers of length 3 There are 375 magic numbers of length 4 There are 750 magic numbers of length 5 There are 1200 magic numbers of length 6 There are 1713 magic numbers of length 7 There are 2227 magic numbers of length 8 There are 2492 magic numbers of length 9 There are 2492 magic numbers of length 10 There are 2225 magic numbers of length 11 There are 2041 magic numbers of length 12 There are 1575 magic numbers of length 13 There are 1132 magic numbers of length 14 There are 770 magic numbers of length 15 There are 571 magic numbers of length 16 There are 335 magic numbers of length 17 There are 180 magic numbers of length 18 There are 90 magic numbers of length 19 There are 44 magic numbers of length 20 There are 18 magic numbers of length 21 There are 12 magic numbers of length 22 There are 6 magic numbers of length 23 There are 3 magic numbers of length 24 There are 1 magic numbers of length 25 There are 0 magic numbers of length 26 Largest magic number is 3608528850368400786036725 Minimally pan-digital(1..9) magic numbers are: 381654729 Minimally pan-digital(0..9) magic numbers are: 3816547290
jq
Adapted from Wren
Works with gojq, the Go implementation of jq, and with fq
The solution presented here depends on the unbounded-precision integer arithmetic of the Go implementations of jq, and the results shown can be generated by an invocation of the form:
gojq -nr -f magic-numbers.jq
def sum(s): reduce s as $x (0; .+$x);
# Emit all the polydivisibles in the form of an array of arrays
# such that the numbers in .[i] are the polydivisibles of length i+1
def polydivisible:
def extend($n):
((. * 10) + range(0;10)) | select(. % $n == 0);
# input: an array of arrays, such that the numbers in .[i] are the polydivisibles of length i+1
def extend:
. as $in
| length as $n
| [$in[-1][] | extend($n+1)] as $x
| if $x|length == 0 then $in
else $in + [$x] | extend
end;
[[range(1;10)]] | extend;
def pandigital:
tostring | gsub("0";"") | explode | unique | length == 9;
# Select the pandigitals from .[$k]
# Input: an array as produced by polydivisible
# Output: an array
def pd($k):
.[$k] | map(select(pandigital));
def tasks:
polydivisible
| .[0] += [0]
| "There are \(sum(.[] | length)) magic numbers in total.",
"\nThe largest is \(.[-1][-1])",
"\nThere are:",
(range(0; length) as $i
| "\(.[$i]|length) with \($i + 1) digit\(if ($i == 0) then "" else "s" end)"),
( "\nAll magic numbers that are pan-digital in 1 through 9 with no repeats: ", pd(8)[] ),
( "\nAll magic numbers that are pan-digital in 0 through 9 with no repeats: ", pd(9)[] ) ;
tasks
- 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
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
Python
from itertools import groupby
def magic_numbers(base):
hist = []
n = l = i = 0
while True:
l += 1
hist.extend((n + digit, l) for digit in range(-n % l, base, l))
i += 1
if i == len(hist):
return hist
n, l = hist[i]
n *= base
mn = magic_numbers(10)
print("found", len(mn), "magic numbers")
print("the largest one is", mn[-1][0])
print("count by number of digits:")
print(*(f"{l}:{sum(1 for _ in g)}" for l, g in groupby(l for _, l in mn)))
print(end="minimally pandigital in 1..9: ")
print(*(m for m, l in mn if l == 9 == len(set(str(m)) - {"0"})))
print(end="minimally pandigital in 0..9: ")
print(*(m for m, l in mn if l == 10 == len(set(str(m)))))
- Output:
found 20457 magic numbers the largest one is 3608528850368400786036725 count by number of 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 minimally pandigital in 1..9: 381654729 minimally pandigital in 0..9: 3816547290
Rust
fn get_digits(mut n: u128) -> [usize; 10] {
let mut digits = [0; 10];
while n > 0 {
digits[(n % 10) as usize] += 1;
n /= 10;
}
digits
}
fn magic_numbers() -> impl std::iter::Iterator<Item = u128> {
let mut magic: Vec<u128> = vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
let mut index = 0;
let mut digits = 2;
std::iter::from_fn(move || {
if index == magic.len() {
let mut magic_new: Vec<u128> = Vec::new();
for &m in &magic {
if m == 0 {
continue;
}
let mut n = 10 * m;
for _ in 0..10 {
if n % digits == 0 {
magic_new.push(n);
}
n += 1;
}
}
index = 0;
digits += 1;
magic = magic_new;
}
if magic.is_empty() {
return None;
}
let m = magic[index];
index += 1;
Some(m)
})
}
fn main() {
let mut count = 0;
let mut dcount = 0;
let mut magic: u128 = 0;
let mut p: u128 = 10;
let digits0 = [1; 10];
let digits1 = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1];
let mut pandigital0: Vec<u128> = Vec::new();
let mut pandigital1: Vec<u128> = Vec::new();
let mut digit_count: Vec<usize> = Vec::new();
for m in magic_numbers() {
magic = m;
if magic >= p {
p *= 10;
digit_count.push(dcount);
dcount = 0;
}
let digits = get_digits(magic);
if digits == digits0 {
pandigital0.push(magic);
} else if digits == digits1 {
pandigital1.push(magic);
}
count += 1;
dcount += 1;
}
digit_count.push(dcount);
println!("There are {} magic numbers.\n", count);
println!("The largest magic number is {}.\n", magic);
println!("Magic number count by digits:");
for (i, c) in digit_count.iter().enumerate() {
println!("{}\t{}", i + 1, c);
}
println!("\nMagic numbers that are minimally pandigital in 1-9:");
for m in pandigital1 {
println!("{}", m);
}
println!("\nMagic numbers that are minimally pandigital in 0-9:");
for m in pandigital0 {
println!("{}", m);
}
}
- 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
Wren
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