A327621 - OEIS

%I #45 Nov 17 2023 21:38:35

%S 3,4,7,9,12,13,16,19,20,23,25,27,28,29,30,31,32,34,36,39,40,43,46,47,

%T 50,52,55,56,59,64,67,68,71,73,76,77,80,81,83,84,85,87,88,89,90,91,92,

%U 93,94,95,96,97,98,100,101,103,104,106,107,108,109,110,111,112

%N Sums of distinct powers of 3 and powers of 4 (greater than 1).

%C From _M. F. Hasler_, Nov 16 2023: (Start)

%C Record gaps in this sequence are : a(2) - a(1) = 1, a(3) - a(2) = 3, a(30) - a(29) = 5, a(112) - a(111) = 39, a(9863) - a(9862) = 1084, a(34096) - a(34095) = 7682, ...

%C These gaps are closely related to the gaps in the set where 3^0 and 4^0 are (both) also allowed to be in the sum, in which case the first missing numbers are A367090 = (62, 63, 143, 144, 207, ...), see also Melfi's paper. It is obvious that the study of these gaps is crucial for the proof of Erdös conjecture.

%C The record gap a(9863) - a(9862) = 1084 explains the discontinuity seen in the graph of a(1..10^4). (End)

%H M. F. Hasler, <a href="/A327621/b327621.txt">Table of n, a(n) for n = 1..10000</a>, Nov 02 2023

%H S. A. Burr, P. Erdős, R. L. Graham, and W. Wen-Ching Li, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa77/aa7722.pdf">Complete sequences of sets of integer powers</a>, Acta Arithmetica 77(2) (1996), 133-138.

%H P. Erdős, <a href="http://members.unine.ch/giuseppe.melfi/erdos2.jpeg">Conjecture about the enumerating function A(x)</a>

%H G. Melfi, <a href="https://doi.org/10.1007/BF02844979">An additive problem about powers of fixed integers</a>, Rend. Circ. Mat. Palermo 50 (2001), 239-246.

%F For A(x) the enumerating function, Erdős conjectured that A(x) > c*x.

%F G. Melfi proved that A(x) > x^0.965 for sufficiently large x.

%e 40 is in the sequence because 40 = 27 + 9 + 4.

%t f[b_, m_] := Select[b Range[0, m/b], Max@ IntegerDigits[#, b] < 2 &]; mx=200; Union@ Select[Total /@ Tuples[{f[3, mx], f[4, mx]}], 0 < # < mx &] (* _Giovanni Resta_, Sep 19 2019 *)

%o (PARI) A327621_upto(N, S=[0])={for(b=3,4, for(k=1, logint(N,b), my(p=b^k); S=setunion(S,[x+p|x<-S,x+p<=N])));S[^1]} \\ _M. F. Hasler_, Nov 02 2023

%o (Python)

%o def A327621_upto(N):

%o     "list(x < N | x = sum(3^j, j in J) + sum(4^k, k in K); J, K subset N*)."

%o     S = {0} # empty sum

%o     for b in (3,4):

%o         p = b

%o         while p < N: S |= {k+p for k in S if k+p < N} ; p *= b

%o     return sorted(S) # includes a(0) = 0, so a(1,2,3,...) = 3,4,9,...

%o # _M. F. Hasler_, Nov 09 2023

%Y Cf. A000244 (powers of 3), A000302 (powers of 4).

%Y Cf. A005836 and A000695 (sums of distinct powers of 3 and of 4).

%K nonn

%O 1,1

%A _Giuseppe Melfi_, Sep 19 2019

%E More terms from _Giovanni Resta_, Sep 19 2019