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).

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

Author

François Marques, Aug 29 2020

Keywords

• nonn
• base
• look

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

Examples

			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
		

Links

• François Marques, Table of n, a(n) for n = 0..10000
• Devansh Singh, Link for Python Program below with comments

Crossrefs

Cf. A077268 (contains digit 0).

Programs

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 *)

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

Formula

a(n) <= (n+1)/2 for n >= 3. - Devansh Singh, Sep 21 2020

Extensions

Minor edits by M. F. Hasler, Oct 26 2020