[math-fun] 5883800000000000 and other pandigital numbers
Yes, 5883800000000000 is pandigital -- in base 14, where it's 75AD3621CB9408. No other pandigital number, in that or any smaller base, is divisible by a higher power of 10. Here's the latest version of my table, showing, for each small base, what's the highest power of each small number that divides any N-digit base-N pandigital number. (As always, this and every table should be viewed in a fixed-width font.) Base: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 2: 1 0 3 1 11 0 5 2 21 0 29 1 36 0 7 3: 0 1 3 5 7 9 10 3 15 17 18 21 23 4: 0 0 1 0 5 0 2 1 10 0 14 0 18 0 3 5: 0 1 2 1 5 5 6 9 9 11 12 13 15 6: 0 0 3 1 1 0 5 2 8 0 3 1 13 0 7: 0 1 2 2 3 1 7 6 8 9 9 13 13 8: 0 0 1 0 3 0 1 0 7 0 9 0 12 0 2 9: 0 0 1 2 3 4 5 1 7 8 9 10 11 10: 0 0 1 1 3 0 5 2 1 0 8 1 11 0 11: 0 1 1 2 2 3 5 7 5 1 8 9 11 12: 0 0 1 0 1 0 2 1 6 0 1 0 10 0 13: 0 0 1 2 2 3 3 5 5 6 8 1 11 14: 0 0 1 0 1 0 2 1 6 0 1 9 1 0 15: 0 1 2 1 2 3 3 3 6 7 6 9 9 1 16: 0 0 0 0 2 0 1 0 5 0 7 0 9 0 1 Note that: For powers of any even number, bases that are congruent to 3 mod 4 have no solutions That's because in any odd base, a number is odd if and only if it has an odd number of odd digits. Any N-digit pandigital number of a length congruent to 3 mod 4 will have an odd number of odd digits, hence every permutation of those digits will represent an odd number. The diagonal values are all 1. That's because in an N-digit pandigital number, there's only one 0, and for a base-N number that digit has to go on the end for the number to be divisible by N. For divisors that are a power of 2, the values are the corresponding values for base 2, divided by which power of 2 it is, rounded down. For instance since the highest power of 2 in any 10-digit base-10 number is 21, the highest power of 16 (2^4) in any 10-digit base-10 number is 21/4 = 5. Analogously with powers of other divisors, e.g. powers of 3 vs. powers of 9 or of 27. That's because base 2^N numbers can be viewed as base-2 numbers chunked in sets of N base-2 digits. Analogously with powers of other divisors. For base N=2^M, the highest power of 2 that will divide an N-digit pandigital number is 2M-1. For instance in base 16 (2^4), it's 7. Again, that's because of chunking. In base 16 (hexadecimal), if the number ends with 80, that's 1000 0000 in base 2 (binary), as every programmer of my generation knows. That's seven 0s. There's no way to get more without a second hexadecimal 0. Questions that remain: Is there an efficient way to fill in the table for higher bases? Currently, I'm testing every N-digit base-N pandigital number for divisibility by every small prime. For each column, especially base 10, where's the first zero, i.e. the smallest number that no N-digit base-N pandigital number is divisible by? Which, if any of these rows and columns belong in OEIS? I don't think any of them are there yet. Where's the error in this post that I will notice immediately after I send it?
Nice table, Keith! I have little to offer, but at least my copy of Mathematica can answer one of your questions by brute force: The first prime that doesn't divide any of the 10! base-10 pandigitals is apparently 111119. (Computing the 10! prime factorizations took under a minute.) --Michael On Tue, Apr 7, 2020 at 11:06 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
Yes, 5883800000000000 is pandigital -- in base 14, where it's 75AD3621CB9408. No other pandigital number, in that or any smaller base, is divisible by a higher power of 10.
Here's the latest version of my table, showing, for each small base, what's the highest power of each small number that divides any N-digit base-N pandigital number. (As always, this and every table should be viewed in a fixed-width font.)
Base: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
2: 1 0 3 1 11 0 5 2 21 0 29 1 36 0 7 3: 0 1 3 5 7 9 10 3 15 17 18 21 23 4: 0 0 1 0 5 0 2 1 10 0 14 0 18 0 3 5: 0 1 2 1 5 5 6 9 9 11 12 13 15 6: 0 0 3 1 1 0 5 2 8 0 3 1 13 0 7: 0 1 2 2 3 1 7 6 8 9 9 13 13 8: 0 0 1 0 3 0 1 0 7 0 9 0 12 0 2 9: 0 0 1 2 3 4 5 1 7 8 9 10 11 10: 0 0 1 1 3 0 5 2 1 0 8 1 11 0 11: 0 1 1 2 2 3 5 7 5 1 8 9 11 12: 0 0 1 0 1 0 2 1 6 0 1 0 10 0 13: 0 0 1 2 2 3 3 5 5 6 8 1 11 14: 0 0 1 0 1 0 2 1 6 0 1 9 1 0 15: 0 1 2 1 2 3 3 3 6 7 6 9 9 1 16: 0 0 0 0 2 0 1 0 5 0 7 0 9 0 1
Note that:
For powers of any even number, bases that are congruent to 3 mod 4 have no solutions
That's because in any odd base, a number is odd if and only if it has an odd number of odd digits. Any N-digit pandigital number of a length congruent to 3 mod 4 will have an odd number of odd digits, hence every permutation of those digits will represent an odd number.
The diagonal values are all 1.
That's because in an N-digit pandigital number, there's only one 0, and for a base-N number that digit has to go on the end for the number to be divisible by N.
For divisors that are a power of 2, the values are the corresponding values for base 2, divided by which power of 2 it is, rounded down. For instance since the highest power of 2 in any 10-digit base-10 number is 21, the highest power of 16 (2^4) in any 10-digit base-10 number is 21/4 = 5. Analogously with powers of other divisors, e.g. powers of 3 vs. powers of 9 or of 27.
That's because base 2^N numbers can be viewed as base-2 numbers chunked in sets of N base-2 digits. Analogously with powers of other divisors.
For base N=2^M, the highest power of 2 that will divide an N-digit pandigital number is 2M-1. For instance in base 16 (2^4), it's 7.
Again, that's because of chunking. In base 16 (hexadecimal), if the number ends with 80, that's 1000 0000 in base 2 (binary), as every programmer of my generation knows. That's seven 0s. There's no way to get more without a second hexadecimal 0.
Questions that remain:
Is there an efficient way to fill in the table for higher bases? Currently, I'm testing every N-digit base-N pandigital number for divisibility by every small prime.
For each column, especially base 10, where's the first zero, i.e. the smallest number that no N-digit base-N pandigital number is divisible by?
Which, if any of these rows and columns belong in OEIS? I don't think any of them are there yet.
Where's the error in this post that I will notice immediately after I send it?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
Having cleaned it up a bit, here's a mathematica brute-force recipe: base = 10 pandigitals = FromDigits[#,base]& /@ Permutations[Range[base]-1]; factorizations = FactorInteger /@ pandigitals; allprimepowers = Join @@ factorizations; (* TimeUsed[] 18 secionds, Length[allprimepowers]==14304281 *) maxpower[_] := 0 updateMaxPower[{p_, exp_}] := maxpower[p] = Max[exp, maxpower[p]] updateMaxPower /@ allprimepowers; (* TimeUsed[] 49 seconds, Length[DownValues[maxpower]]==1102174, so there are 1102173 primes dividing some pandigital *) Now it's easy to generate the values in the prime-numbered rows of the 10's column of Keith's array: Table[{Prime[n],maxpower[Prime[n]]}, {n,1000}] {{2, 21}, {3, 15}, {5, 9}, {7, 8}, {11, 5}, {13, 5}, {17, 5}, {19, 4}, {23, 4}, {29, 4}, {31, 4}, {37, 3}, {41, 3}, {43, 4}, {47, 3}, {53, 4}, {59, 3}, {61, 3}, {67, 3}, {71, 3}, {73, 3}, {79, 3}, {83, 3}, {89, 3}, {97, 3}, {101, 2}, {103, 3}, {107, 3}, {109, 3}, {113, 3}, {127, 2}, {131, 3}, {137, 3}, {139, 3}, {149, 3}, {151, 3}, {157, 3}, {163, 2}, {167, 3}, {173, 2}, {179, 3}, {181, 2}, {191, 3}, {193, 2}, {197, 2}, {199, 2}, {211, 2}, {223, 2}, {227, 2}, {229, 3}, {233, 2}, {239, 2}, {241, 2}, {251, 3}, {257, 2}, {263, 2}, {269, 2}, {271, 2}, {277, 2}, {281, 2}, {283, 3}, {293, 2}, {307, 2}, {311, 2}, {313, 2}, {317, 2}, {331, 2}, {337, 2}, {347, 2}, {349, 3}, {353, 2}, {359, 2}, {367, 2}, {373, 2}, {379, 2}, {383, 2}, {389, 2}, {397, 2}, {401, 3}, {409, 2}, {419, 2}, {421, 2}, {431, 2}, {433, 2}, {439, 2}, {443, 2}, {449, 2}, {457, 2}, {461, 2}, {463, 2}, {467, 2}, {479, 3}, {487, 2}, {491, 2}, {499, 2}, {503, 2}, {509, 2}, {521, 2}, {523, 2}, {541, 3}} (I guess doing the composite-numbered rows would involve some factor/round/max logic that I haven't written but isn't hard.) To find the first 0 in the column, i.e. the first missing prime: For[n=1, maxpower[Prime[n]] > 0, n++, Null] {n, Prime[n]} (* Answer: {10545, 111119} *) The first zero in the base-6 column is 229, and in base-8 is 4663. None of this counts as "efficient", certainly, since the work grows as worse than the factorial of the base. --Michael On Wed, Apr 8, 2020 at 2:29 PM Michael Kleber <michael.kleber@gmail.com> wrote:
Nice table, Keith!
I have little to offer, but at least my copy of Mathematica can answer one of your questions by brute force: The first prime that doesn't divide any of the 10! base-10 pandigitals is apparently 111119. (Computing the 10! prime factorizations took under a minute.)
--Michael
On Tue, Apr 7, 2020 at 11:06 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
Yes, 5883800000000000 is pandigital -- in base 14, where it's 75AD3621CB9408. No other pandigital number, in that or any smaller base, is divisible by a higher power of 10.
Here's the latest version of my table, showing, for each small base, what's the highest power of each small number that divides any N-digit base-N pandigital number. (As always, this and every table should be viewed in a fixed-width font.)
Base: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
2: 1 0 3 1 11 0 5 2 21 0 29 1 36 0 7 3: 0 1 3 5 7 9 10 3 15 17 18 21 23 4: 0 0 1 0 5 0 2 1 10 0 14 0 18 0 3 5: 0 1 2 1 5 5 6 9 9 11 12 13 15 6: 0 0 3 1 1 0 5 2 8 0 3 1 13 0 7: 0 1 2 2 3 1 7 6 8 9 9 13 13 8: 0 0 1 0 3 0 1 0 7 0 9 0 12 0 2 9: 0 0 1 2 3 4 5 1 7 8 9 10 11 10: 0 0 1 1 3 0 5 2 1 0 8 1 11 0 11: 0 1 1 2 2 3 5 7 5 1 8 9 11 12: 0 0 1 0 1 0 2 1 6 0 1 0 10 0 13: 0 0 1 2 2 3 3 5 5 6 8 1 11 14: 0 0 1 0 1 0 2 1 6 0 1 9 1 0 15: 0 1 2 1 2 3 3 3 6 7 6 9 9 1 16: 0 0 0 0 2 0 1 0 5 0 7 0 9 0 1
Note that:
For powers of any even number, bases that are congruent to 3 mod 4 have no solutions
That's because in any odd base, a number is odd if and only if it has an odd number of odd digits. Any N-digit pandigital number of a length congruent to 3 mod 4 will have an odd number of odd digits, hence every permutation of those digits will represent an odd number.
The diagonal values are all 1.
That's because in an N-digit pandigital number, there's only one 0, and for a base-N number that digit has to go on the end for the number to be divisible by N.
For divisors that are a power of 2, the values are the corresponding values for base 2, divided by which power of 2 it is, rounded down. For instance since the highest power of 2 in any 10-digit base-10 number is 21, the highest power of 16 (2^4) in any 10-digit base-10 number is 21/4 = 5. Analogously with powers of other divisors, e.g. powers of 3 vs. powers of 9 or of 27.
That's because base 2^N numbers can be viewed as base-2 numbers chunked in sets of N base-2 digits. Analogously with powers of other divisors.
For base N=2^M, the highest power of 2 that will divide an N-digit pandigital number is 2M-1. For instance in base 16 (2^4), it's 7.
Again, that's because of chunking. In base 16 (hexadecimal), if the number ends with 80, that's 1000 0000 in base 2 (binary), as every programmer of my generation knows. That's seven 0s. There's no way to get more without a second hexadecimal 0.
Questions that remain:
Is there an efficient way to fill in the table for higher bases? Currently, I'm testing every N-digit base-N pandigital number for divisibility by every small prime.
For each column, especially base 10, where's the first zero, i.e. the smallest number that no N-digit base-N pandigital number is divisible by?
Which, if any of these rows and columns belong in OEIS? I don't think any of them are there yet.
Where's the error in this post that I will notice immediately after I send it?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
-- Forewarned is worth an octopus in the bush.
For base 12, I had to change my Mathematica thing to not materialize all those lists of 12! things all at once, since they wouldn't fit in memory. After 10 hours and 22Gb of RAM, the first prime not dividing any of the pandigitals is 3257447. Since base-12 took over 250x as long as base-10, I don't think base-14 is going to happen this way. --Michael In[1]:= base=12 In[2]:= maxpower[_] := 0 In[3]:= updateMaxPower[{p_, exp_}] := maxpower[p] = Max[exp, maxpower[p]] In[4]:= Needs["Combinatorica`"] In[5]:= For[n=base!;perm=Range[base]-1, n>0, n--;perm=NextPermutation[perm], updateMaxPower /@ FactorInteger[FromDigits[perm,base]]] In[6]:= TimeUsed[] Out[6]= 36059.9 In[7]:= Table[{Prime[n],maxpower[Prime[n]]}, {n,100}] //InputForm Out[7]= {{2, 29}, {3, 18}, {5, 12}, {7, 9}, {11, 8}, {13, 8}, {17, 7}, {19, 6}, {23, 6}, {29, 6}, {31, 5}, {37, 5}, {41, 5}, {43, 5}, {47, 6}, {53, 5}, {59, 4}, {61, 4}, {67, 4}, {71, 4}, {73, 4}, {79, 4}, {83, 4}, {89, 4}, {97, 4}, {101, 4}, {103, 4}, {107, 4}, {109, 4}, {113, 4}, {127, 3}, {131, 4}, {137, 3}, {139, 3}, {149, 3}, {151, 4}, {157, 4}, {163, 3}, {167, 3}, {173, 4}, {179, 4}, {181, 3}, {191, 3}, {193, 3}, {197, 3}, {199, 4}, {211, 4}, {223, 3}, {227, 3}, {229, 3}, {233, 4}, {239, 3}, {241, 3}, {251, 3}, {257, 3}, {263, 4}, {269, 3}, {271, 3}, {277, 3}, {281, 3}, {283, 3}, {293, 3}, {307, 3}, {311, 3}, {313, 3}, {317, 3}, {331, 4}, {337, 3}, {347, 3}, {349, 3}, {353, 3}, {359, 3}, {367, 3}, {373, 3}, {379, 3}, {383, 3}, {389, 3}, {397, 3}, {401, 3}, {409, 3}, {419, 3}, {421, 3}, {431, 3}, {433, 3}, {439, 3}, {443, 3}, {449, 3}, {457, 3}, {461, 3}, {463, 3}, {467, 3}, {479, 3}, {487, 3}, {491, 3}, {499, 3}, {503, 3}, {509, 3}, {521, 3}, {523, 3}, {541, 3}} In[8]:= {n, Prime[n]} Out[8]= {234070, 3257447} On Thu, Apr 9, 2020 at 11:22 AM Michael Kleber <michael.kleber@gmail.com> wrote:
Having cleaned it up a bit, here's a mathematica brute-force recipe:
base = 10 pandigitals = FromDigits[#,base]& /@ Permutations[Range[base]-1]; factorizations = FactorInteger /@ pandigitals; allprimepowers = Join @@ factorizations; (* TimeUsed[] 18 secionds, Length[allprimepowers]==14304281 *)
maxpower[_] := 0 updateMaxPower[{p_, exp_}] := maxpower[p] = Max[exp, maxpower[p]] updateMaxPower /@ allprimepowers; (* TimeUsed[] 49 seconds, Length[DownValues[maxpower]]==1102174, so there are 1102173 primes dividing some pandigital *)
Now it's easy to generate the values in the prime-numbered rows of the 10's column of Keith's array:
Table[{Prime[n],maxpower[Prime[n]]}, {n,1000}] {{2, 21}, {3, 15}, {5, 9}, {7, 8}, {11, 5}, {13, 5}, {17, 5}, {19, 4}, {23, 4}, {29, 4}, {31, 4}, {37, 3}, {41, 3}, {43, 4}, {47, 3}, {53, 4}, {59, 3}, {61, 3}, {67, 3}, {71, 3}, {73, 3}, {79, 3}, {83, 3}, {89, 3}, {97, 3}, {101, 2}, {103, 3}, {107, 3}, {109, 3}, {113, 3}, {127, 2}, {131, 3}, {137, 3}, {139, 3}, {149, 3}, {151, 3}, {157, 3}, {163, 2}, {167, 3}, {173, 2}, {179, 3}, {181, 2}, {191, 3}, {193, 2}, {197, 2}, {199, 2}, {211, 2}, {223, 2}, {227, 2}, {229, 3}, {233, 2}, {239, 2}, {241, 2}, {251, 3}, {257, 2}, {263, 2}, {269, 2}, {271, 2}, {277, 2}, {281, 2}, {283, 3}, {293, 2}, {307, 2}, {311, 2}, {313, 2}, {317, 2}, {331, 2}, {337, 2}, {347, 2}, {349, 3}, {353, 2}, {359, 2}, {367, 2}, {373, 2}, {379, 2}, {383, 2}, {389, 2}, {397, 2}, {401, 3}, {409, 2}, {419, 2}, {421, 2}, {431, 2}, {433, 2}, {439, 2}, {443, 2}, {449, 2}, {457, 2}, {461, 2}, {463, 2}, {467, 2}, {479, 3}, {487, 2}, {491, 2}, {499, 2}, {503, 2}, {509, 2}, {521, 2}, {523, 2}, {541, 3}}
(I guess doing the composite-numbered rows would involve some factor/round/max logic that I haven't written but isn't hard.)
To find the first 0 in the column, i.e. the first missing prime:
For[n=1, maxpower[Prime[n]] > 0, n++, Null] {n, Prime[n]} (* Answer: {10545, 111119} *)
The first zero in the base-6 column is 229, and in base-8 is 4663.
None of this counts as "efficient", certainly, since the work grows as worse than the factorial of the base.
--Michael
On Wed, Apr 8, 2020 at 2:29 PM Michael Kleber <michael.kleber@gmail.com> wrote:
Nice table, Keith!
I have little to offer, but at least my copy of Mathematica can answer one of your questions by brute force: The first prime that doesn't divide any of the 10! base-10 pandigitals is apparently 111119. (Computing the 10! prime factorizations took under a minute.)
--Michael
On Tue, Apr 7, 2020 at 11:06 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
Yes, 5883800000000000 is pandigital -- in base 14, where it's 75AD3621CB9408. No other pandigital number, in that or any smaller base, is divisible by a higher power of 10.
Here's the latest version of my table, showing, for each small base, what's the highest power of each small number that divides any N-digit base-N pandigital number. (As always, this and every table should be viewed in a fixed-width font.)
Base: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
2: 1 0 3 1 11 0 5 2 21 0 29 1 36 0 7 3: 0 1 3 5 7 9 10 3 15 17 18 21 23 4: 0 0 1 0 5 0 2 1 10 0 14 0 18 0 3 5: 0 1 2 1 5 5 6 9 9 11 12 13 15 6: 0 0 3 1 1 0 5 2 8 0 3 1 13 0 7: 0 1 2 2 3 1 7 6 8 9 9 13 13 8: 0 0 1 0 3 0 1 0 7 0 9 0 12 0 2 9: 0 0 1 2 3 4 5 1 7 8 9 10 11 10: 0 0 1 1 3 0 5 2 1 0 8 1 11 0 11: 0 1 1 2 2 3 5 7 5 1 8 9 11 12: 0 0 1 0 1 0 2 1 6 0 1 0 10 0 13: 0 0 1 2 2 3 3 5 5 6 8 1 11 14: 0 0 1 0 1 0 2 1 6 0 1 9 1 0 15: 0 1 2 1 2 3 3 3 6 7 6 9 9 1 16: 0 0 0 0 2 0 1 0 5 0 7 0 9 0 1
Note that:
For powers of any even number, bases that are congruent to 3 mod 4 have no solutions
That's because in any odd base, a number is odd if and only if it has an odd number of odd digits. Any N-digit pandigital number of a length congruent to 3 mod 4 will have an odd number of odd digits, hence every permutation of those digits will represent an odd number.
The diagonal values are all 1.
That's because in an N-digit pandigital number, there's only one 0, and for a base-N number that digit has to go on the end for the number to be divisible by N.
For divisors that are a power of 2, the values are the corresponding values for base 2, divided by which power of 2 it is, rounded down. For instance since the highest power of 2 in any 10-digit base-10 number is 21, the highest power of 16 (2^4) in any 10-digit base-10 number is 21/4 = 5. Analogously with powers of other divisors, e.g. powers of 3 vs. powers of 9 or of 27.
That's because base 2^N numbers can be viewed as base-2 numbers chunked in sets of N base-2 digits. Analogously with powers of other divisors.
For base N=2^M, the highest power of 2 that will divide an N-digit pandigital number is 2M-1. For instance in base 16 (2^4), it's 7.
Again, that's because of chunking. In base 16 (hexadecimal), if the number ends with 80, that's 1000 0000 in base 2 (binary), as every programmer of my generation knows. That's seven 0s. There's no way to get more without a second hexadecimal 0.
Questions that remain:
Is there an efficient way to fill in the table for higher bases? Currently, I'm testing every N-digit base-N pandigital number for divisibility by every small prime.
For each column, especially base 10, where's the first zero, i.e. the smallest number that no N-digit base-N pandigital number is divisible by?
Which, if any of these rows and columns belong in OEIS? I don't think any of them are there yet.
Where's the error in this post that I will notice immediately after I send it?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
-- Forewarned is worth an octopus in the bush.
-- Forewarned is worth an octopus in the bush.
participants (2)
-
Keith F. Lynch -
Michael Kleber