A239703 Number of bases b > 1 for which the base-b digital sum of n is b.

0, 0, 0, 1, 0, 2, 1, 2, 0, 2, 2, 2, 1, 4, 0, 2, 1, 3, 1, 4, 1, 4, 2, 1, 1, 4, 1, 1, 2, 4, 0, 5, 0, 5, 3, 1, 2, 7, 0, 2, 3, 5, 0, 4, 0, 4, 3, 1, 1, 5, 1, 3, 2, 3, 0, 5, 2, 6, 1, 1, 0, 8, 0, 2, 2, 5, 3, 5, 1, 2, 2, 4, 1, 8, 0, 1, 4, 3, 2, 4, 1, 6, 3, 2, 0, 10, 2

Offset: 0

Author

Hieronymus Fischer, Mar 31 2014

Keywords

• nonn

Comments

For the definition of the digital sum, see A007953.

For reference, we write digitSum_b(x) for the base-b digital sum of x according to A007953 (with general base b).

The bases counted exclude the special base 1. The base-1 expansion of a natural number is defined as 1=1_1, 2=11_1, 3=111_1 and so on. As a result, the base-1 digital sum of n is n. The inclusion of base b = 1 would lead to a(1) = 1 instead of a(1) = 0. All other terms remain unchanged.

For odd n > 1 and b := (n + 1)/2 we have digitSum_b(n) = b, and thus a(n) >= 1.

The digitSum_b(n) is < b for bases b which satisfy b > floor((n+1)/2), and thus a(n) <= floor((n+1)/2).

If b is a base such that the base-b digital sum of n is b, then b < n and b - 1 is a divisor of n - 1, thus the number of such bases is limited by the number of divisors of n - 1 (see formula section).

If p < n - 1 is a divisor of n - 1 which satisfy p >= sqrt(n - 1), then digitSum_b(n) = b for b := p + 1. This leads to a lower bound for a(n) (see formula section).

If b - 1 is a divisor of n - 1, then b is not necessarily a base such that base-b digital sum of n is b. Example: 1, 2, 3, 4, 6, 8, 12, 16, and 24 are the divisors < 48 of 48, but digitSum_2(49) = 3, digitSum_3(49) = 5, digitSum_5(49) = 9, digitSum_7(49) = 1.

a(b*n) > 0 for all b > 1 which satisfy digitSum_b(n) = b.

Example 1: digitSum_2(3) = 2, hence a(2*3) > 0.

Example 2: digitSum_3(5) = 3, hence a(3*5) > 0.

The first n with a(n) = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ... are n = 3, 5, 17, 13, 31, 57, 37, 61, 81, 85, ... .

Examples

			a(1) = 1, since digitSum_1(1) = 1 and digitSum_b(1) <> b for all b > 1.
a(2) = 0, since digitSum_1(2) = 2 (because of 2 = 11_1), and digitSum_2(2) = 1 (because of 2 = 10_2), and digitSum_b(2) = 2 for all b > 2.
a(3) = 1, since digitSum_1(3) = 3 (because of 3 = 111_1), and digitSum_2(3) = 2 (because of 3 = 11_2), and digitSum_3(3) = 1 (because of 3 = 10_3), and digitSum_b(3) = 3 for all b > 3.
a(5) = 2, since digitSum_1(5) = 5 (because of 5 = 11111_1), and digitSum_2(5) = 2 (because of 5 = 101_2), and digitSum_3(5) = 3 (because of 5 = 12_3), and digitSum_4(5) = 2 (because of 5 = 11_4), and digitSum_5(5) = 1 (because of 5 = 10_5), and digitSum_b(5) = 5 for all b > 5.
		

Links

• Hieronymus Fischer, Table of n, a(n) for n = 0..10000

Crossrefs

Cf. A007953, A079696, A008864, A187813, A239707, A239708.

Cf. A000040; A000005 (definition of sigma_0(n)).

Programs

Smalltalk

"> Version 1: simple calculation for small numbers.
  Answer the number of bases b such that the digital sum of n in base b is b.
  Valid for bases b >= 1, thus returning a(1) = 1.
  Using digitalSum from A007953.
  Usage: n numOfBasesWithAltDigitalSumEQBase
  Answer: a(n)"
numOfBasesWithDigitalSumEQBase
  | numBases b bmax |
  numBases := 0.
  bmax := self + 1 // 2.
  b := 0.
  [b < bmax] whileTrue: [
     b := b + 1
     (self digitalSum: b) = b
     ifTrue: [numBases := numBases + 1]].
  ^numBases
-----------
"> Version 2: accelerated calculation for large numbers.
  Answer the number of bases b such that the digital sum of n in base b is b.
  Valid for bases b > 1, thus returning a(1) = 0.
  Using digitalSum from A007953.
  Usage: n numOfBasesWithAltDigitalSumEQBase
  Answer: a(n)"
numOfBasesWithDigitalSumEQBase
  | numBases div b bsize |
  self < 3 ifTrue: [^0].
  div := (self - 1) divisors.
  numBases := 0.
  bsize := div size - 1.
  1 to: bsize do: [ :i | b := (div at: i) + 1.
   (self digitalSum: b) = b
       ifTrue: [numBases := numBases + 1] ].
  ^numBases

Formula

a(n) = 0, if and only if n is a term of A187813.

a(A187813(n)) = 0.

a(A239708(n)) = 1, for n > 0.

a(A018900(n)) > 0, for n > 0.

a(A079696(n)) > 0, for n > 0.

a(A008864(n)) <= 1, for n > 0.

a(n) <= 1, if n - 1 is a prime.

a(n) <= sigma_0(n - 1) - 1, for n > 1.

a(n) >= floor((sigma_0(n-1)-1)/2), for n > 1.