login
A337496
Number of bases b for which the expansion of n in base b contains the largest digit possible (i.e., the digit b-1).
8
0, 1, 2, 2, 2, 3, 3, 4, 3, 3, 2, 5, 3, 4, 5, 5, 3, 5, 3, 6, 5, 5, 4, 8, 4, 4, 4, 5, 3, 8, 4, 6, 5, 5, 6, 8, 2, 3, 4, 7, 2, 7, 4, 7, 8, 7, 6, 11, 6, 7, 5, 6, 4, 8, 6, 8, 6, 6, 5, 12, 5, 6, 8, 7, 5, 7, 4, 7, 5, 9, 5, 12, 5, 6, 7, 7, 7, 9, 5, 11, 5, 3, 2, 11, 4, 3, 4, 8, 3, 11, 5
OFFSET
0,3
COMMENTS
An integer b > 1 is a main base of n if n in base b contains the largest digit possible (i.e., the digit b-1).
2 is a main base for all nonzero integers because in binary, they start with the digit 1.
10 is a main base for all numbers with a 9 in their decimal expansion.
b = n+1 is a main base of n when n > 0.
A000005(n+1) - 1 <= a(n) <= ceiling(sqrt(n+1)) + floor(A000005(n+1)/2) - 1 for n > 0. Indeed, if b != 1 is a divisor of n+1 then n = (k-1)*b + b-1 so the last digit of n in base b is b-1. On the other side, n = q*b + r with r < b. So if b is a main base of n then either r = b-1 (and b is a divisor of n+1) or b is a main base of q and therefore b-1 <= q which implies (b-1)^2 < n (i.e., b <= floor(sqrt(n))+1 <= ceiling(sqrt(n+1)) ). But if b > sqrt(n+1) is a divisor of (n+1) then (n+1)/b < sqrt(n+1) is another divisors of n+1 and only half of them can be greater than its square root. - François Marques, Dec 07 2020
FORMULA
a(n) <= (n+1)/2 for n >= 3. - Devansh Singh, Sep 21 2020
EXAMPLE
For n = 7, a(7) = 4 because the main bases of 7 are 2, 3, 4 and 8 as shown in the table below:
Base b | 2 | 3 | 4 | 5 | 6 | 7 | 8
-----------------+-----+-----+-----+-----+-----+-----+-----
7 in base b | 111 | 21 | 13 | 12 | 11 | 10 | 7
-----------------+-----+-----+-----+-----+-----+-----+-----
b is a main base | yes | yes | yes | no | no | no | yes
MAPLE
A337496 := proc(n)
local k, r:=0;
for k from 2 to n+1 do
if max(convert(n, base, k)) = k - 1 then
r++;
end if;
end do;
return r;
end proc:
seq(A337496(n), n=0..90);
MATHEMATICA
baseQ[n_, b_] := MemberQ[IntegerDigits[n, b], b - 1]; a[n_] := Count[Range[2, n + 1], _?(baseQ[n, #] &)]; Array[a, 100, 0] (* Amiram Eldar, Sep 01 2020 *)
PROG
(PARI) a(n) = sum(b=2, n+1, vecmax(digits(n, b)) == b-1); \\ Michel Marcus, Aug 30 2020
(PARI) a337496(n) = my(last_pos(v, k) = forstep(j=#v, 1, -1, if(v[j]==k, return(#v-j))); return(-1); , s=ceil(sqrt(n+1)), p); (n==0) + 1 + sum(b=2, s, p=last_pos(digits(n, b), b-1); if(p<0, 0, p==0, 2, 1)) -((n+1)==s^2) -2*((n+1)==s*(s-1)); \\ François Marques, Dec 07 2020
(Python)
def A337496(N):
A337496_n=[0, 1]
for j in range(2, N+1):
A337496_n.append(2)
for b in range(3, ((N+1)//2) +1):
n=2*b-1
while n<=N:
s=0
m=n//b
while m%b==b-2:
s=s+1
m=m//b
x=b*((b**s)-1)//(b-1)
for i in range(n, min(N, x+n)+1):
A337496_n[i]+=1
n=n+x+b
return(A337496_n)
print(A337496(100)) # Devansh Singh, Dec 30 2020
CROSSREFS
Cf. A077268 (contains digit 0).
Sequence in context: A238337 A104484 A038809 * A078342 A177903 A107325
KEYWORD
nonn,base,look
AUTHOR
François Marques, Aug 29 2020
EXTENSIONS
Minor edits by M. F. Hasler, Oct 26 2020
STATUS
approved