|
| |
|
|
A245439
|
|
The number of ways in which n is equal to the sum of digits taken from the numbers <= n.
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
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)
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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)
|
|
|
PROG
|
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,base
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
