%I #24 Sep 04 2023 22:20:04
%S 1,1,2,2,3,4,5,6,8,26,81,243,693,1887,4932,12418,30288,72026,167989,
%T 541500,1635975,4662579,12580587,32228307,78662108,183988734,
%U 415466897,912816164,1965020012,6121555788,17573354640,46896718806
%N The number of ways in which n is equal to the sum of digits taken from the numbers <= n.
%C Let the range (1,n) in base 10 be represented in the form (1.A,n.A) = (1.A, 2.A, 3.A...n.A), where digit A = 10 in bases >= 11. Let samplesum(d(i),i=1..n) sum solitary digits d(i) sampled from each member of (1.A,n.A) (i.e., only one digit at a time is sampled from a particular number). The list above is the number of ways in which n = samplesum(d(i),i=1..n) when 0 <= d(i) < A for all i. Because d(i) is permitted to equal 0, sums like these are counted separately:
%C 10 = 1 + 2 + 3 + 4
%C 10 = 1 + 2 + 3 + 4 + 0 (of 10)
%C 11 = 1 + 2 + 3 + 4 + 1 (of 11)
%C 11 = 1 + 2 + 3 + 4 + 0 (of 10) + 1 (of 11)
%C 12 = 1 + 2 + 3 + 6
%C 12 = 1 + 2 + 3 + 6 + 0 (of 10)
%C These two sums are also counted separately:
%C 11 = 1 + 2 + 3 + 4 + 1 (first digit of 11)
%C 11 = 1 + 2 + 3 + 4 + 1 (second digit of 11)
%C However, this sum is excluded:
%C 11 = 2 + 3 + 4 + 1 (first digit of 11) + 1 (second digit of 11)
%e 1 = 1 (sum=1)
%e 2 = 2 (s=1)
%e 3 = 1 + 2; 3 (s=2)
%e 4 = 1 + 3; 4 (s=2)
%e 5 = 2 + 3; 1 + 4; 5 (s=3)
%e 6 = 1 + 2 + 3; 2 + 4; 1 + 5; 6 (s=4)
%e 7 = 1 + 2 + 4; 3 + 4; 2 + 5; 1 + 6; 7 (s=5)
%e 8 = 1 + 3 + 4; 1 + 2 + 5; 3 + 5; 2 + 6; 1 + 7; 8 (s=6)
%e 9 = 2 + 3 + 4; 1 + 3 + 5; 4 + 5; 1 + 2 + 6; 3 + 6; 2 + 7; 1 + 8; 9 (s=8)
%e 10 = 1 + 2 + 3 + 4; 2 + 3 + 5; 1 + 4 + 5; 1 + 3 + 6; 4 + 6; 1 + 2 + 7; 3 + 7; 2 + 8; 1 + 9; 1 + 2 + 3 + 4 + 0 (of 10); 2 + 3 + 5 + 0 (of 10); 1 + 4 + 5 + 0 (of 10); 1 + 3 + 6 + 0 (of 10); 4 + 6 + 0 (of 10); 1 + 2 + 7 + 0 (of 10); 3 + 7 + 0 (of 10); 2 + 8 + 0 (of 10); 1 + 9 + 0 (of 10); 2 + 3 + 4 + 1 (of 10); 1 + 3 + 5 + 1 (of 10); 4 + 5 + 1 (of 10); 1 + 2 + 6 + 1 (of 10); 3 + 6 + 1 (of 10); 2 + 7 + 1 (of 10); 1 + 8 + 1 (of 10); 9 + 1 (of 10) (s=26)
%o (PARI) /* To exclude 0 from sums, change "dn[i]>=0" to "dn[i]>0" */
%o { nmx=20; b=10; d = vector(nmx+1); s = vector(nmx+1); for(n=1,nmx+1, dn=digits(n,b); nn=0; for(i=1,#dn,if(dn[i]>=0,nn=nn*b+dn[i])); d[n]=nn; ); for(n=1,nmx, si=1; c=0; until(si>n, nn=0; for(i=1,si,if(s[i]>0,nn+=(d[i]\b^(s[i]-1))%b);if(nn>n,i=si)); if(nn==n,c++); incs();
%o ); s[si]=0; print1(c,", ")); break; }
%o {incs() = s[1]++; i=1; while(d[i]\b^(s[i]-1)==0, s[i]=0; i++; s[i]++; ); if(i>si,si=i); } \\ _Anthony Sand_, Aug 19 2014
%o A245439(n) = my(X = 'x + O('x^(n+1))); polcoef( prod(i=1,n, 1 + vecsum( apply(t->X^t, digits(i)) ) ), n); \\ _Max Alekseyev_, Sep 04 2023
%Y Cf. A000009, A000041, A245438, A241754.
%K nonn,base
%O 1,3
%A _Anthony Sand_, Jul 22 2014
%E More terms from _Max Alekseyev_, Sep 04 2023