|
| |
|
|
A348209
|
|
a(n) is the smallest positive integer k such that the base-n representation of 2^k has a pandigital ending of length n, or 0 if no such k exists.
|
|
1
|
|
|
|
1, 5, 0, 34, 33, 20, 0, 1689, 7386, 1971, 34180, 43983, 262717, 37576, 0, 617963, 2818633, 2136492, 5325278, 140997161, 572340185, 1140209730, 800810806, 5573697257, 6694155083, 15533636306, 220798644390
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
2,2
|
|
|
COMMENTS
|
The base-n representations under consideration are assumed to be without leading zeros. A base-n pandigital string is any string of base-n digits that contains all of them (strings beginning with 0 are admitted).
The base-n representation of a positive integer x has an ending of length n iff x >= n^(n-1). The base-n representations of two such integers have the same ending of length n iff these numbers are congruent modulo n^n.
a(n) = 0 whenever n is a power of 2 other than 2 itself. This is because powers of 2 in power-of-2 bases can have only two distinct digits. Is a(n) equal to 0 for any other values of n?
Let n be a positive integer that is not a power of 2. Then n = (2^u)*v, where u is a nonnegative integer, and v is an odd number greater than 1. Let d be the multiplicative order of 2 modulo v^n (of course, d <= phi(v^n) where phi is Euler's totient function). Suppose k is an integer such that 2^k >= n^(n-1). Then the base-n representation of 2^(k+d) has the same ending of length n as the base-n representation of 2^k. This can be shown by proving that 2^(k+d) and 2^k are congruent modulo n^n. One may reason as follows. Since 2^(k+d) - 2^k = 2^k*(2^d - 1), n^n = 2^(u*n)*v^n, and the number 2^d - 1 is divisible by v^n, it is sufficient to prove that k >= u*n. This inequality holds indeed because 2^k/2^(u*n) >= n^(n-1)/(2^u)^n = v^n/n > 1.
Suppose now there is a positive integer k such that the base-n representation of 2^k for the considered n has a pandigital ending of length n. The least such integer is a(n), and, by the statement proved above, the inequality 2^k < n^(n-1)*2^d holds for this k (otherwise the base-n representation of 2^(k-d) would have the same ending of length n as the one of 2^k). Thus a(n) is an algorithmically computable function of n. (Unfortunately, due to enormous values of d, the algorithm derived from the above reasoning seems to be of no practical use for the actual computation of a(n) in the possibly existing cases when n is not a power of 2, but the base-n representation of no power of 2 has a pandigital ending with length n.)
a(n) > 0 for all integers n between 2 and 200 that are not powers of 2, with the possible exception of the numbers 80, 96, 112, 144, 160, 168, 176, 184 and 192. For those of the above-mentioned integers n with a(n) > 0 that are greater than 28, corresponding numbers k are presented such that the base-n representation of 2^k has a pandigital ending with length n. These k were found by appropriately using Euler's totient theorem, and they can be seen in an uploaded file.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
a(5) = 34 because the base-5 representation of 2^34 is 240141021303214 and thus has the ending 03214, whereas none of the base-5 representations of the previous powers of 2 ends with a pandigital string of length 5.
|
|
|
PROG
|
(Python)
from labmath import multord
def w(r, n):
z, s=r, set()
while z%n not in s:
s.add(z%n)
z=z//n
return len(s)
def a(n):
if n==2: return 1
else:
v=n
while v%2==0: v=v//2
if v==1: return 0
else:
k, r, m=0, 1, n**(n-1)
while r<m: k, r=k+1, 2*r
M, e=m*n, k+multord(2, v**n)
while (w(r, n)<n) and (k<e): k, r=k+1, 2*r%M
if w(r, n)==n: return k
else: return 0
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,base,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
