A383327 a(n) is the number of occurrences of n in A049802.

1, 2, 1, 4, 1, 2, 3, 5, 1, 3, 2, 5, 2, 4, 1, 7, 2, 4, 2, 5, 3, 5, 1, 6, 3, 4, 2, 6, 3, 3, 2, 10, 3, 4, 1, 5, 4, 5, 3, 8, 3, 5, 2, 6, 2, 5, 2, 10, 3, 4, 2, 7, 2, 5, 3, 8, 4, 5, 2, 5, 2, 7, 1, 14, 1, 5, 5, 5, 1, 4, 4, 11, 3, 6, 3, 7, 2, 6, 2, 10, 2, 6, 3, 8, 3, 6, 4, 11

Offset: 1

Author

Miles Englezou, Apr 23 2025

Keywords

• nonn

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).

Examples

			 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)
		

Links

• Miles Englezou, Proof of bound
• Wikipedia, P-adic number

Crossrefs

Cf. A049802, A000041.

Programs

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)

Formula

a(n) <= A000041(n).