cp's OEIS Frontend

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

%I A337496 #117 Mar 18 2021 08:15:59
%S A337496 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,
%T A337496 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,
%U A337496 7,5,9,5,12,5,6,7,7,7,9,5,11,5,3,2,11,4,3,4,8,3,11,5
%N 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).
%C A337496 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).
%C A337496 2 is a main base for all nonzero integers because in binary, they start with the digit 1.
%C A337496 10 is a main base for all numbers with a 9 in their decimal expansion.
%C A337496 b = n+1 is a main base of n when n > 0.
%C A337496 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
%H A337496 François Marques, <a href="/A337496/b337496.txt">Table of n, a(n) for n = 0..10000</a>
%H A337496 Devansh Singh, <a href="http://bit.ly/3cAsrjv">Link for Python Program below with comments</a>
%F A337496 a(n) <= (n+1)/2 for n >= 3. - _Devansh Singh_, Sep 21 2020
%e A337496 For n = 7, a(7) = 4 because the main bases of 7 are 2, 3, 4 and 8 as shown in the table below:
%e A337496           Base b |   2 |   3 |   4 |   5 |   6 |   7 |   8
%e A337496 -----------------+-----+-----+-----+-----+-----+-----+-----
%e A337496      7 in base b | 111 |  21 |  13 |  12 |  11 |  10 |   7
%e A337496 -----------------+-----+-----+-----+-----+-----+-----+-----
%e A337496 b is a main base | yes | yes | yes |  no |  no |  no | yes
%p A337496 A337496 := proc(n)
%p A337496 local k, r:=0;
%p A337496 for k from 2 to n+1 do
%p A337496    if max(convert(n, base, k)) = k - 1 then
%p A337496       r++;
%p A337496    end if;
%p A337496 end do;
%p A337496 return r;
%p A337496 end proc:
%p A337496 seq(A337496(n), n=0..90);
%t A337496 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 *)
%o A337496 (PARI) a(n) = sum(b=2, n+1, vecmax(digits(n, b)) == b-1); \\ _Michel Marcus_, Aug 30 2020
%o A337496 (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
%o A337496 (Python)
%o A337496 def A337496(N):
%o A337496     A337496_n=[0,1]
%o A337496     for j in range(2,N+1):
%o A337496         A337496_n.append(2)
%o A337496     for b in range(3,((N+1)//2) +1):
%o A337496         n=2*b-1
%o A337496         while n<=N:
%o A337496             s=0
%o A337496             m=n//b
%o A337496             while m%b==b-2:
%o A337496                 s=s+1
%o A337496                 m=m//b
%o A337496             x=b*((b**s)-1)//(b-1)
%o A337496             for i in range(n, min(N,x+n)+1):
%o A337496                 A337496_n[i]+=1
%o A337496             n=n+x+b
%o A337496     return(A337496_n)
%o A337496 print(A337496(100)) # _Devansh Singh_, Dec 30 2020
%Y A337496 Cf. A077268 (contains digit 0).
%K A337496 nonn,base,look
%O A337496 0,3
%A A337496 _François Marques_, Aug 29 2020
%E A337496 Minor edits by _M. F. Hasler_, Oct 26 2020