A245439 The number of ways in which n is equal to the sum of digits taken from the numbers <= n.

1, 1, 2, 2, 3, 4, 5, 6, 8, 26, 81, 243, 693, 1887, 4932, 12418, 30288, 72026, 167989, 541500, 1635975, 4662579, 12580587, 32228307, 78662108, 183988734, 415466897, 912816164, 1965020012, 6121555788, 17573354640, 46896718806

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 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:

10 = 1 + 2 + 3 + 4

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

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

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

12 = 1 + 2 + 3 + 6

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

These two sums are also counted separately:

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

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

However, this sum is excluded:

11 = 2 + 3 + 4 + 1 (first digit of 11) + 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; 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)
		

Crossrefs

Cf. A000009, A000041, A245438, A241754.

Programs

PARI

/* To exclude 0 from 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 19 2014
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

Extensions

More terms from Max Alekseyev, Sep 04 2023