cp's OEIS Frontend

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

%I A383327 #42 May 14 2025 19:09:06
%S A383327 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,
%T A383327 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,
%U A383327 5,1,4,4,11,3,6,3,7,2,6,2,10,2,6,3,8,3,6,4,11
%N A383327 a(n) is the number of occurrences of n in A049802.
%C A383327 The offset is 1 since A049802(k) = 0 for infinitely many values (when k = 2^r, r >= 0).
%C A383327 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).
%C A383327 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.
%C A383327 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).
%H A383327 Miles Englezou, <a href="/A383327/a383327_6.pdf">Proof of bound</a>
%H A383327 Wikipedia, <a href="https://en.wikipedia.org/wiki/P-adic_number">P-adic number</a>
%F A383327 a(n) <= A000041(n).
%e A383327  n |a(n)| k such that A049802(k) = n
%e A383327 ---+----+------------------------------------
%e A383327  1 | 1  | {3}
%e A383327  2 | 2  | {5, 6}
%e A383327  3 | 1  | {9}
%e A383327  4 | 4  | {7, 10, 12, 17}
%e A383327  5 | 1  | {33}
%e A383327  6 | 2  | {18, 65}
%e A383327  7 | 3  | {11, 13, 129}
%e A383327  8 | 5  | {14, 20, 24, 34, 257}
%e A383327  9 | 1  | {513}
%e A383327 10 | 3  | {19, 66, 1025}
%e A383327 11 | 2  | {15, 2049}
%e A383327 12 | 5  | {21, 25, 36, 130, 4097}
%e A383327 13 | 2  | {35, 8193}
%e A383327 14 | 4  | {22, 26, 258, 16385}
%e A383327 15 | 1  | {32769}
%e A383327 16 | 7  | {28, 40, 48, 67, 68, 514, 65537}
%e A383327 17 | 2  | {37, 131073}
%e A383327 18 | 4  | {23, 27, 1026, 262145}
%e A383327 19 | 2  | {131, 524289}
%e A383327 20 | 5  | {29, 38, 132, 2050, 1048577}
%e A383327 21 | 3  | {41, 49, 2097153}
%e A383327 22 | 5  | {30, 69, 259, 4098, 4194305}
%e A383327 23 | 1  | {8388609}
%e A383327 24 | 6  | {42, 50, 72, 260, 8194, 16777217}
%e A383327 25 | 3  | {39, 515, 33554433}
%e A383327 26 | 4  | {31, 70, 16386, 67108865}
%e A383327 ---------------------------------------------
%e A383327 Let (x_1, ..., x_k) be the tuple of summands as described in the comments.
%e A383327 Then for:
%e A383327 n = 4, a(4) = 4
%e A383327   7: (1, 3)
%e A383327   10: (0, 2, 2)
%e A383327   12: (0, 0, 4)
%e A383327   17: (1, 1, 1, 1)
%e A383327 n = 12, a(12) = 5
%e A383327   21: (1, 1, 5, 5)
%e A383327   25: (1, 1, 1, 9)
%e A383327   36: (0, 0, 4, 4, 4)
%e A383327   130: (0, 2, 2, 2, 2, 2, 2)
%e A383327   4097: (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
%e A383327 n = 20, a(20) = 5
%e A383327   29: (1, 1, 5, 13)
%e A383327   38: (0, 2, 6, 6, 6)
%e A383327   132: (0, 0, 4, 4, 4, 4, 4)
%e A383327   2050: (0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2)
%e A383327   1048577: (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
%o A383327 (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)
%o A383327 (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)
%Y A383327 Cf. A049802, A000041.
%K A383327 nonn
%O A383327 1,2
%A A383327 _Miles Englezou_, Apr 23 2025