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

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)

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.

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.

Example

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

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

Prog

(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

Crossrefs

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

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

Sequence in context: A032729 A035270 A120451 * A060428 A352274 A035238

Adjacent sequences: A327618 A327619 A327620 * A327622 A327623 A327624

Keyword

nonn

Author

Giuseppe Melfi, Sep 19 2019

Extensions

More terms from Giovanni Resta, Sep 19 2019

Status

approved