Howdy! I've confirmed that, at least through base 8300 or so, the smallest x that yields the longest period is exactly that seed that is b^n/t, where t is the largest value < b with no prime divisors not also prime divisors of b. I have a cleaner proof that makes this more clear, and also shows that this is the case. If there is interest in the cleaner proof I can post it. The outline is simply: 1. Handle prime b and x ending in 0 first. Then essentially eliminate the digit 0 from consideration and only use 1..b-1 (this makes the rest slightly easier). 2. Define k(b,x,n) which is x in base b but focusing only on the lower order n digits. 3. Show k(b,x,n) where gcd(x,b^n)<b never includes the b-1 digit. 4. Show k(b,x,n) where gcd(x,b^n)>b always includes all digits at digit position n-1, and k(b,x,n) <= k(b,gcd(x,b^n),n); this lets us restrict attention to divisors of b^n when trying to find the max k. 6. Show that k(b,b^n/t)=(b-1)t when b^n/t is an integer and t<b.
From there it's clear all we need do is maximize b^n/t for t in divisors of b^n and t<b and we've got both the seed (b^n/t) and the length ((b-1)t).
The numbers do indeed get big. On Sat, Jan 7, 2012 at 9:38 AM, David Wilson <davidwwilson@comcast.net> wrote:
To reiterate the problem:
For base b >= 2, to find the least k(b) such that for any x >= 1, the values {x, 2x, ..., kx} written in base-b together must include all the base-b digits.
Tom Rokicki gives the following solution (I assume his proof is good, I did not check it thoroughly):
k(b) = b, if b is prime (b-1)*A079277(n), otherwise.
I confirmed that this seems to match brute-force computations for small b.
But then I became interested in x(b), the smallest x that requires k(b) multiples to include every base-b digit.
As an example, I originally posed the problem for base b = 10. Tom's solution gives k(10) = 72, that is, for any x >= 1, all the base-10 digits occur among the base-10 representations of {x, 2x, ..., 72x}, and 72 is necessary for some x, the smallest being x = 125, so that x(10) = 125.
Assuming k(b) is correct, I tried computing x(b) (the smallest x requiring k(b)) by brute force for small b (via a C++ program), and got (for 2 <= b <= 33):
1,1,2,1,9,1,2,3,125,1,16,1,343,25,2,1,6561,1,25,49,14641,1,32,5,28561,3,49,1,1000,1,2,1331
From this sparse evidence, I conjecture that every prime divisor of x(b) is a divisor of b. x(30) = 1000 refutes the conjecture that x(b) is always a prime power. Tom Rokicki's proof gives x(p) = 1 for prime p as a corollary. I conjecture x(p^n) = p for higher prime powers.
The computations for x(34) ran for more than a minute without results. So I gave up on brute force and narrowed the candidates to x(34) = 2^x*17^y based on my conjecture about the prime divisors of x(b). I was able to find x = 1419857 = 17^5 requiring k = k(34) = 1056, so we have x(34) <= 17^5, with almost certain equality.
One might conjecture x(2p) = p^n with n = ceil(log2(p)) or thereabouts. If that is the case, x(2p) grows large very quickly, far beyond brute force computability (by testing each x >= 1). The x(b) prime divisor conjecture, if true, makes the search space tractable, but the sheer size of the numbers involved make it more suitable problem for Mma or such as opposed to what I have at my disposal.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --