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

1, 1, 2, 2, 3, 4, 5, 6, 8, 17, 53, 158, 450, 1224, 3195, 8036, 19585, 46549, 108541, 219677, 664149, 1891075, 5091680, 13004347, 31632641, 73745789, 166055768, 364027232, 782374631, 1462836178, 4198493416, 11171538552, 27755958012

Offset: 1

Author

Anthony Sand, Jul 22 2014

Keywords

• nonn
• base

Comments

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:

10 = 1 + 2 + 3 + 4.

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

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

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

12 = 1 + 2 + 3 + 6.

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

However, these two sums are counted separately:

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

11 = 1 + 2 + 3 + 4 + 1 (second digit of 11).

Examples

			1 = 1 (sum=1).
2 = 2 (s=1).
3 = 1 + 2; 3 (s=2).
4 = 1 + 3; 4 (s=2).
5 = 2 + 3; 1 + 4; 5 (s=3).
6 = 1 + 2 + 3; 2 + 4; 1 + 5; 6 (s=4).
7 = 1 + 2 + 4; 3 + 4; 2 + 5; 1 + 6; 7 (s=5).
8 = 1 + 3 + 4; 1 + 2 + 5; 3 + 5; 2 + 6; 1 + 7; 8 (s=6).
9 = 2 + 3 + 4; 1 + 3 + 5; 4 + 5; 1 + 2 + 6; 3 + 6; 2 + 7; 1 + 8; 9 (s=8).
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).
11 = 3 + 4 + 5 + 1 (of 10).
12 = 1 + 2 + 5 + 1 (of 10) + 1 (of 11) + 2 (of 12).
13 = 1 + 2 + 6 + 1 (of 11) + 2 (of 12).
14 = 3 + 4 + 1 (of 10) + 1 (of 11) + 2 (of 12) + 3 (of 13).
15 = 3 + 5 + 1 (of 10) + 2 (of 12) + 3 (of 13) + 1 (of 14).
		

Crossrefs

Cf. A241754, A245439.

Programs

PARI

/* To include 0 in sums, change "dn[i]>0" to "dn[i]>=0" */
{ 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; }
{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
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

Extensions

More terms from Max Alekseyev, Sep 04 2023