A239704 Number of bases b for which the base-b alternate digital sum of n is b.

1, 0, 1, 0, 2, 0, 1, 0, 1, 0, 2, 0, 1, 0, 1, 0, 2, 0, 3, 1, 1, 0, 3, 0, 1, 0, 1, 0, 3, 0, 1, 0, 1, 1, 1, 0, 1, 0, 2, 0, 2, 0, 1, 0, 1, 0, 2, 0, 2, 0, 1, 0, 3, 1, 2, 0, 1, 0, 3, 0, 1, 0, 1, 0, 2, 0, 1, 1, 1, 0, 3, 0, 1, 0, 1, 1, 3, 0, 1, 1, 1, 0, 5, 0, 1, 1, 1, 0, 4, 0, 2, 1, 1, 0, 3, 0, 1, 0, 3, 0

Offset: 1

Author

Hieronymus Fischer, May 08 2014

Keywords

• nonn

Comments

For the definition of the alternate digital sum, see A055017 or A225693.

For reference: we write altDigitSum_b(x) for the base-b alternate digital sum of x according to A055017.

The number of counted bases includes 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 alternate digital sum is 0 if n is even, and is 1 if n is odd.

For odd n we have altDigitSum_1(n) = 1, and thus a(n) >= 1.

The altDigitSum_b(n) is < b for bases b that satisfy b > b0 := floor((sqrt(4n+5) - 1)/2), and thus a(n) <= b0. This boundary can also be expressed as b0 := floor(sqrt(n - floor(sqrt(n)) + 1)).

If n + 1 is an oblong number (see A002378), then b := (sqrt(4n+5) - 1)/2 is an integer equal to b0 and b^2 + b - 1 = n. This implies altDigitSum_b(n) = 1 + 0 + b - 1 = b and shows, that there are infinitely many n with a base b > 1 such that altDigitSum_b(n) = b. It follows a(n) >= 2 for n = 5, 11, 19, 29, 41, ... (since those n are odd).

Moreover, a(n) >= 2 is also true for n == b(b+1)-1 (mod (b+1)b^3), b>1.

Example 1: altDigitSum_2(n) = 2 for n == 5 (mod 24).

Example 2: altDigitSum_3(n) = 3 for n == 11 (mod 108).

Example 3: altDigitSum_4(n) = 4 for n == 19 (mod 320).

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

If b + 1 is a divisor of n + 1, then b is not necessarily a base such that base-b alternate digital sum of n is b. Example: 2, 3, 4, 6 and 12 are divisors of 12, and altDigitSum_1(11) = 1, altDigitSum_3(11) = 3, but altDigitSum_2(11) = -1, altDigitSum_5(11) = -1, altDigitSum_11(11) = -1.

a(b*n) > (b*n) mod 2 for all b > 1 which satisfy altDigitSum_b(n) = -b.

Example 4: altDigitSum_2(10) = -2, hence a(2*10) > 0

Example 5: altDigitSum_3(33) = -3, hence a(3*33) > 1

The first n with a(n) = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ... are n = 1, 5, 19, 89, 83, 359, 419, 1259, 839, 3359, ... .

Examples

			a(1) = 1, since altDigitSum_1(1) = 1 and altDigitSum_b(1) = 1 < b for all b > 1.
a(2) = 0, since altDigitSum_1(2) = 0 (because of 2 = 11_1), and altDigitSum_2(2) = -1 (because of 2 = 10_2), and altDigitSum_b(2) = 2 < b for all b > 2.
a(3) = 1, since altDigitSum_1(3) = 1 (because of 3 = 111_1), and altDigitSum_2(3) = 0 (because of 3 = 11_2), and altDigitSum_3(3) = -1 (because of 3 = 10_3), and altDigitSum_b(3) = 3 < b for all b > 3.
a(5) = 2, since altDigitSum_1(5) = 1 (because of 5 = 11111_1), and altDigitSum_2(5) = 2 (because of 5 = 101_2), and altDigitSum_3(5) = 1 (because of 5 = 12_3), and altDigitSum_4(5) = 0 (because of 5 = 11_4), and altDigitSum_5(5) = 1 (because of 5 = 10_5), and altDigitSum_b(5) = 5 < b for all b > 5.
		

Links

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

Crossrefs

Cf. A055017, A225693, A187813.

Cf. A239703, A239705, A239706, A239707.

Cf. A002378, A008864, A000040, A000005.

Programs

Smalltalk

"> Version 1: simple calculation for small numbers.
  Answer the number of bases b for which the alternate
  digital sum of n in base b is b. Valid for bases b > 0.
  Usage: n numOfBasesWithAltDigitalSumEQ0
  Answer: a(n)"
  numOfBasesWithAltDigitalSumEQBase
     | b q numBases |
     self < 2 ifTrue: [^0].
     numBases := 1.
     q := self sqrtTruncated.
     b := 1.
     [b < q] whileTrue:[
          (self altDigitalSumRight: b) = 0
          ifTrue: [numBases := numBases + 1].
          b := b + 1].
  ^numBases
[by Hieronymus Fischer, May 08 2014]
-----------

Smalltalk

"> Version 2: accelerated calculation for large numbers.
   Answer the number of bases b for which the alternate
   digital sum of n in base b is b."
   numOfBasesWithAltDigitalSumEQBase
     | numBases div b bsize |
     div := (self + 1) divisors.
     numBases := 0.
     bsize := div size // 2 + 1.
     2 to: bsize
         do:
             [:i |
              b := (div at: i) - 1.
             [(self altDigitalSumRight: b) = b
                  ifTrue: [numBases := numBases + 1]]].
  ^numBases
[by Hieronymus Fischer, May 08 2014]

Formula

a(A002378(n)-1) = a(n^2+n-1) >= 2, for n > 1.

a(n) = 0, if n + 1 is a prime.

a(n) <= floor(sigma_0(n+1)/2).