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

3, 4, 7, 9, 12, 13, 16, 19, 20, 23, 25, 27, 28, 29, 30, 31, 32, 34, 36, 39, 40, 43, 46, 47, 50, 52, 55, 56, 59, 64, 67, 68, 71, 73, 76, 77, 80, 81, 83, 84, 85, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 100, 101, 103, 104, 106, 107, 108, 109, 110, 111, 112

Offset: 1

Author

Giuseppe Melfi, Sep 19 2019

Keywords

• nonn

Comments

From M. F. Hasler, Nov 16 2023: (Start)

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

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.

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

Examples

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

Links

• M. F. Hasler, Table of n, a(n) for n = 1..10000, Nov 02 2023
• S. A. Burr, P. Erdős, R. L. Graham, and W. Wen-Ching Li, Complete sequences of sets of integer powers, Acta Arithmetica 77(2) (1996), 133-138.
• P. Erdős, Conjecture about the enumerating function A(x)
• G. Melfi, An additive problem about powers of fixed integers, Rend. Circ. Mat. Palermo 50 (2001), 239-246.

Crossrefs

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

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

Programs

Mathematica

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

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

Python

def A327621_upto(N):
    "list(x < N | x = sum(3^j, j in J) + sum(4^k, k in K); J, K subset N*)."
    S = {0} # empty sum
    for b in (3,4):
        p = b
        while p < N: S |= {k+p for k in S if k+p < N} ; p *= b
    return sorted(S) # includes a(0) = 0, so a(1,2,3,...) = 3,4,9,...
# M. F. Hasler, Nov 09 2023

Formula

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

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

Extensions

More terms from Giovanni Resta, Sep 19 2019