login
a(n) = the number of ways in which n is equal to the sum of digits > 0 taken from numbers <= n.
2

%I #18 Sep 04 2023 22:20:00

%S 1,1,2,2,3,4,5,6,8,17,53,158,450,1224,3195,8036,19585,46549,108541,

%T 219677,664149,1891075,5091680,13004347,31632641,73745789,166055768,

%U 364027232,782374631,1462836178,4198493416,11171538552,27755958012

%N a(n) = the number of ways in which n is equal to the sum of digits > 0 taken from 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 single digits d(i) sampled from each member of (1.A,n.A). 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 not permitted to equal 0, sums like these are not counted separately:

%C 10 = 1 + 2 + 3 + 4.

%C 10 = 1 + 2 + 3 + 4 + 0 (of 10).

%C 11 = 1 + 2 + 3 + 4 + 0 (of 10) + 1 (of 11).

%C 11 = 1 + 2 + 3 + 4 + 1 (of 11).

%C 12 = 1 + 2 + 3 + 6.

%C 12 = 1 + 2 + 3 + 6 + 0 (of 10).

%C However, these two sums are counted separately:

%C 11 = 1 + 2 + 3 + 4 + 1 (first digit of 11).

%C 11 = 1 + 2 + 3 + 4 + 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; 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=17).

%e 11 = 3 + 4 + 5 + 1 (of 10).

%e 12 = 1 + 2 + 5 + 1 (of 10) + 1 (of 11) + 2 (of 12).

%e 13 = 1 + 2 + 6 + 1 (of 11) + 2 (of 12).

%e 14 = 3 + 4 + 1 (of 10) + 1 (of 11) + 2 (of 12) + 3 (of 13).

%e 15 = 3 + 5 + 1 (of 10) + 2 (of 12) + 3 (of 13) + 1 (of 14).

%o (PARI) /* To include 0 in 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(); ); 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 15 2014

%o A245438(n) = my(X = 'x + O('x^(n+1))); polcoef( prod(i=1,n, 1 + vecsum(apply(t->(t>0)*X^t,digits(i))) ), n); \\ _Max Alekseyev_, Sep 04 2023

%Y Cf. A241754, A245439.

%K nonn,base

%O 1,3

%A _Anthony Sand_, Jul 22 2014

%E More terms from _Max Alekseyev_, Sep 04 2023