OFFSET
1,2
COMMENTS
The offset is 1 since A049802(k) = 0 for infinitely many values (when k = 2^r, r >= 0).
Every m > 0 in A049802 has a finite multiplicity, since, except for n = 2, the range of numbers for which A049802(k) = s is bounded above by 2^s+1 (see Englezou link).
The tuple of summands (x_1, ..., x_t) for m in A049802 can also be seen as a finite subset of an infinite tuple which is the representation of m as a profinite integer isomorphic to the normalized 2-adic series of m. This is because m is an element of the inverse limit of the finite rings Z/(2^i)Z, which is a profinite group isomorphic to the ring of 2-adic integers. In the infinite tuple (x_1, x_2, ...), x_i = m for every i such that m < 2^i. For example, for m = 29, we have the tuple (1, 1, 5, 13, 29, 29, 29, ...). See the Wikipedia link for more information.
From a combinatorial perspective, the tuple of summands (x_1, ..., x_t) mentioned above can be seen as a set of t counters, where the j-th counter cycles through 0 to 2^j-1. The natural question 'which m in A049802 appear k times?' becomes a question about how this cycling condition restricts the number of tuples which sum to m. For example, for n <= 100, when n = 1, 3, 5, 9, 15, 23, 35, 63, 65, and 67 there is only one m such that the tuple of summands sums to n (a trivial tuple consisting of n 1s, trivial because there is such a tuple for every n >= 1, i.e. for every m = 2^n+1).
LINKS
FORMULA
a(n) <= A000041(n).
EXAMPLE
n |a(n)| k such that A049802(k) = n
---+----+------------------------------------
1 | 1 | {3}
2 | 2 | {5, 6}
3 | 1 | {9}
4 | 4 | {7, 10, 12, 17}
5 | 1 | {33}
6 | 2 | {18, 65}
7 | 3 | {11, 13, 129}
8 | 5 | {14, 20, 24, 34, 257}
9 | 1 | {513}
10 | 3 | {19, 66, 1025}
11 | 2 | {15, 2049}
12 | 5 | {21, 25, 36, 130, 4097}
13 | 2 | {35, 8193}
14 | 4 | {22, 26, 258, 16385}
15 | 1 | {32769}
16 | 7 | {28, 40, 48, 67, 68, 514, 65537}
17 | 2 | {37, 131073}
18 | 4 | {23, 27, 1026, 262145}
19 | 2 | {131, 524289}
20 | 5 | {29, 38, 132, 2050, 1048577}
21 | 3 | {41, 49, 2097153}
22 | 5 | {30, 69, 259, 4098, 4194305}
23 | 1 | {8388609}
24 | 6 | {42, 50, 72, 260, 8194, 16777217}
25 | 3 | {39, 515, 33554433}
26 | 4 | {31, 70, 16386, 67108865}
---------------------------------------------
Let (x_1, ..., x_k) be the tuple of summands as described in the comments.
Then for:
n = 4, a(4) = 4
7: (1, 3)
10: (0, 2, 2)
12: (0, 0, 4)
17: (1, 1, 1, 1)
n = 12, a(12) = 5
21: (1, 1, 5, 5)
25: (1, 1, 1, 9)
36: (0, 0, 4, 4, 4)
130: (0, 2, 2, 2, 2, 2, 2)
4097: (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
n = 20, a(20) = 5
29: (1, 1, 5, 13)
38: (0, 2, 6, 6, 6)
132: (0, 0, 4, 4, 4, 4, 4)
2050: (0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2)
1048577: (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
PROG
(PARI) a(n) = my(S=[], s); if(n==2, return(2)); for(m=1, 2^n+1, s=sum(k=1, logint(m, 2), m%2^k); if(n==s, S=concat(S, m))); return(#S)
(PARI) a(n) = local(tuple_sum, section, expansion, T=[], breakout, S, K); (tuple_sum(m) = sum(k=1, logint(m, 2), m % 2^k)); (section(r) = my(S=[]); for(n=1, 2^(r+1), if(logint(n, 2)==r, S=concat(S, n))); return(S[#S/2+1..#S])); (expansion(a, l) = my(k=a, K=[]); K=concat(K, a); for(n=1, l-1, K=concat(K, k+2^(logint(a, 2)-1+n)); k=k+2^(logint(a, 2)-1+n)); return(K)); for(k=1, n, for(i=1, #section(k), breakout=0; if(tuple_sum(section(k)[1]) > n, breakout=1); K=expansion(section(k)[i], n); for(j=1, #K, if(tuple_sum(K[j]) > n, break, if(tuple_sum(K[j])==n, T=concat(T, K[j]); break)))); if(breakout==1, break)); return(#T)
CROSSREFS
KEYWORD
nonn
AUTHOR
Miles Englezou, Apr 23 2025
STATUS
approved