cp's OEIS Frontend

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

%I A239703 #30 Oct 25 2014 14:42:21
%S A239703 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,
%T A239703 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,
%U A239703 1,2,2,4,1,8,0,1,4,3,2,4,1,6,3,2,0,10,2
%N A239703 Number of bases b > 1 for which the base-b digital sum of n is b.
%C A239703 For the definition of the digital sum, see A007953.
%C A239703 For reference, we write digitSum_b(x) for the base-b digital sum of x according to A007953 (with general base b).
%C A239703 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.
%C A239703 For odd n > 1 and b := (n + 1)/2 we have digitSum_b(n) = b, and thus a(n) >= 1.
%C A239703 The digitSum_b(n) is < b for bases b which satisfy b > floor((n+1)/2), and thus a(n) <= floor((n+1)/2).
%C A239703 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).
%C A239703 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).
%C A239703 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.
%C A239703 a(b*n) > 0 for all b > 1 which satisfy digitSum_b(n) = b.
%C A239703   Example 1: digitSum_2(3) = 2, hence a(2*3) > 0.
%C A239703   Example 2: digitSum_3(5) = 3, hence a(3*5) > 0.
%C A239703 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, ... .
%H A239703 Hieronymus Fischer, <a href="/A239703/b239703.txt">Table of n, a(n) for n = 0..10000</a>
%F A239703 a(n) = 0, if and only if n is a term of A187813.
%F A239703 a(A187813(n)) = 0.
%F A239703 a(A239708(n)) = 1, for n > 0.
%F A239703 a(A018900(n)) > 0, for n > 0.
%F A239703 a(A079696(n)) > 0, for n > 0.
%F A239703 a(A008864(n)) <= 1, for n > 0.
%F A239703 a(n) <= 1, if n - 1 is a prime.
%F A239703 a(n) <= sigma_0(n - 1) - 1, for n > 1.
%F A239703 a(n) >= floor((sigma_0(n-1)-1)/2), for n > 1.
%e A239703 a(1) = 1, since digitSum_1(1) = 1 and digitSum_b(1) <> b for all b > 1.
%e A239703 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.
%e A239703 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.
%e A239703 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.
%o A239703 (Smalltalk)
%o A239703 "> Version 1: simple calculation for small numbers.
%o A239703   Answer the number of bases b such that the digital sum of n in base b is b.
%o A239703   Valid for bases b >= 1, thus returning a(1) = 1.
%o A239703   Using digitalSum from A007953.
%o A239703   Usage: n numOfBasesWithAltDigitalSumEQBase
%o A239703   Answer: a(n)"
%o A239703 numOfBasesWithDigitalSumEQBase
%o A239703   | numBases b bmax |
%o A239703   numBases := 0.
%o A239703   bmax := self + 1 // 2.
%o A239703   b := 0.
%o A239703   [b < bmax] whileTrue: [
%o A239703      b := b + 1
%o A239703      (self digitalSum: b) = b
%o A239703      ifTrue: [numBases := numBases + 1]].
%o A239703   ^numBases
%o A239703 -----------
%o A239703 "> Version 2: accelerated calculation for large numbers.
%o A239703   Answer the number of bases b such that the digital sum of n in base b is b.
%o A239703   Valid for bases b > 1, thus returning a(1) = 0.
%o A239703   Using digitalSum from A007953.
%o A239703   Usage: n numOfBasesWithAltDigitalSumEQBase
%o A239703   Answer: a(n)"
%o A239703 numOfBasesWithDigitalSumEQBase
%o A239703   | numBases div b bsize |
%o A239703   self < 3 ifTrue: [^0].
%o A239703   div := (self - 1) divisors.
%o A239703   numBases := 0.
%o A239703   bsize := div size - 1.
%o A239703   1 to: bsize do: [ :i | b := (div at: i) + 1.
%o A239703    (self digitalSum: b) = b
%o A239703        ifTrue: [numBases := numBases + 1] ].
%o A239703   ^numBases
%Y A239703 Cf. A007953, A079696, A008864, A187813, A239707, A239708.
%Y A239703 Cf. A000040; A000005 (definition of sigma_0(n)).
%K A239703 nonn
%O A239703 0,6
%A A239703 _Hieronymus Fischer_, Mar 31 2014