Calculating Pandigital Numbers

[Flexico]

Inspired by a passage in the book Things to Make and Do in the Fourth Dimension, I threw together an algorithm to find all existing pandigital numbers in a given base. It uses a brute force method utilizing the itertools.permutations function, checking every possible combination of digits. This works well enough for bases up to 11, but beyond that the calculation time goes out of control, as the time function increases with the factorial of one minus the input base. A quick calculation tells me completion of my project (through base 64) would take over 6x10^73 years. Personally, I plan to have moved on to other projects by then.

Does anyone have any more efficient method of testing for pandigital numbers?

[Larz60+]

Doesn't sound like something that we all do every day.

[Ofnuts]

Inspired by a passage in the book Things to Make and Do in the Fourth Dimension, I threw together an algorithm to find all existing pandigital numbers in a given base. It uses a brute force method utilizing the itertools.permutations function, checking every possible combination of digits. This works well enough for bases up to 11, but beyond that the calculation time goes out of control, as the time function increases with the factorial of one minus the input base. A quick calculation tells me completion of my project (through base 64) would take over 6x10^73 years. Personally, I plan to have moved on to other projects by then.

Does anyone have any more efficient method of testing for pandigital numbers?

The strict definition (all digits used at least once) means that there is an infinite number of pandigital numbers in any given base.

A more restrictive definition (all digits used exactly once, and no zero on left) still produces (n-1)! numbers, but you don't need to "test" them, just generate them, and yes, 63! is a big number...

[Flexico]

Inspired by a passage in the book Things to Make and Do in the Fourth Dimension, I threw together an algorithm to find all existing pandigital numbers in a given base. It uses a brute force method utilizing the itertools.permutations function, checking every possible combination of digits. This works well enough for bases up to 11, but beyond that the calculation time goes out of control, as the time function increases with the factorial of one minus the input base. A quick calculation tells me completion of my project (through base 64) would take over 6x10^73 years. Personally, I plan to have moved on to other projects by then.

Does anyone have any more efficient method of testing for pandigital numbers?

The strict definition (all digits used at least once) means that there is an infinite number of pandigital numbers in any given base.

A more restrictive definition (all digits used exactly once, and no zero on left) still produces (n-1)! numbers, but you don't need to "test" them, just generate them, and yes, 63! is a big number...

Yes, I'm using the "every number used exactly once with no zeros" definition. And generating all the possibilities is pretty straightforward (if time-consuming), but how do I know which ones are pandigital?

Oh wait -- I should specify. I'm searching for the ones that follow the rule of the first digit being divisible by 1, the first two digits being divisible by 2, etc. I forgot that's not included in the definition for "pandigital" heh. The only one in base 10 is 381,654,729 for example. That's what I meant by testing.

[micseydel]

I'm searching for the ones that follow the rule of the first digit being divisible by 1, the first two digits being divisible by 2, etc. I forgot that's not included in the definition for "pandigital" heh. The only one in base 10 is 381,654,729 for example.

Do you mean "the second digit being divisible by 2"? Or are you looking at the product? Your example isn't great here.

Have you tried to write a function to test this? Is it non-functional, or simply inefficient? In either case, what example(s) demonstrate the problem?

[Flexico]

I'm searching for the ones that follow the rule of the first digit being divisible by 1, the first two digits being divisible by 2, etc. I forgot that's not included in the definition for "pandigital" heh. The only one in base 10 is 381,654,729 for example.

Do you mean "the second digit being divisible by 2"? Or are you looking at the product? Your example isn't great here.

Have you tried to write a function to test this? Is it non-functional, or simply inefficient? In either case, what example(s) demonstrate the problem?

My apologies, the source made it sound like this was a well-known puzzle. 3 is divisible by 1, 38 is divisible by 2, 381 is divisible by 3, 3816 is divisible by 4, etc. It works for the whole number.

My function is perfectly working and reliable; the problem is when I get into bases higher than 12, it takes many days to compute, and when I get into even higher bases we're talking on the scale of the birth and death of galaxies. XD

I attached my code for you to test if you like. The "flex" library is just a bunch of functions I wrote that I use in many programs, such as my base conversion function.

[Ofnuts]

Oh wait -- I should specify. I'm searching for the ones that follow the rule of the first digit being divisible by 1, the first two digits being divisible by 2, etc. I forgot that's not included in the definition for "pandigital" heh. The only one in base 10 is 381,654,729 for example. That's what I meant by testing.

You don't need to "test" either. These are fairly restrictive conditions... For instance in base 10 the 2nd digit must be [0,2,4,6,8], the 5th digit must be 0 or 5... Once you have defined the first two digits, there are only 3 possibilities for the 3rd digit... So you don't need to generate them all. So you end up traveling a tree where each branch is a digit in the final number, but you will find that most branches are dead-ends.

But of course the divisibility criteria are different in each numeral base (the only common one, divisibility by N-1, is unfortunately always true for your pandigital numbers). But you can also compute the next possible digits by brute force, this would still be a lot faster than generating them all.