A113028

[pmb]

A while back, I poked at a diverting math problem for a bit, and then ended up submitting it to The online encyclopedia of integer sequences where it got accepted. At the same time, it lit a fire in jes5199's brain. Now it has mutated into some kind of crazy bizarro super speed demon of something: ( Read more... )

Comments

[conform]

naive approach: consider every number in descending order to see if it contains no 0s in base n representation, no duplicate digits, and is divisible by each digit.

note: if a number's digits base n all divide it, then the lcm of all of those digits also divides it.

note: if a particular set of digits base n (or subset of digits) has a least common multiple (LCM) which is a multiple of the base, then multiples of the lcm which contain that subset of digits will always end in 0. so we can shortcut testing for any number which contains those digits.

josh-c approach: build lexical permutations in descending order, starting from the most significant digit (MSD) and working to the lsd. at each digit, compute LCM (previous digits, current digit) and test for divisibility by the base. if we reach the final digit, test if number % lcm is 0. if it is, we're done.

jesse approach: for descending lengths of subsets of digits (e.g., start with all digits < n, then consider all sets with one digit missing, etc), compute lcm for each set of

[kirinn]

I have no idea whether this means anything, but it occurred to me to wonder for which bases your number uses the maximum amount of digits. Assuming the answers given so far are right, we have:
2, 4, 8, 16, 32...

Gosh, that looks fairly well determined. Now I wonder if I'm missing something (relatively) obvious, or if the reason is subtle.

Also, only a few bases actually have an answer with *fewer* digits than the previous base: 12, 20, 24, 28, 30, 33, 35... er, on second thought, it becomes rather common at high bases.

[conform]

we can see right off the bat that we'll never be able to eliminate digit sets for bases that are powers of two via the lcm(digits) % base = 0 test.

lcm(digits) is basically the union of the prime factors of each digit, preserving repetitions from each prime factorization but eliminating duplication in the union (so pf(8) = {2,2,2} and pf(6) = {2,3} and lcm(8,6) = 2*2*2*3, not 2*2*2*3*2). lcm(digits) % base = 0 is expressing that pf(base) is a subset of lcm(digits). clearly no number smaller than 8 can have three 2s in its prime factorization.

we can generalize this to say that the lcm test will fail for any base that can be expressed as an integer power > 1 -- squares, cubes, etc -- and primes.

most other bases (all others? i want to say yes, but i'm not positive. certainly every base that has a prime factorization without repeating primes) have subsets that get disqualified by the lcm rule, which means we immediately skip the full set of numbers.

[misuba]

Math is hard.