A367090 Numbers that cannot be written as a sum of distinct powers of 3 and distinct powers of 4.

62, 63, 143, 144, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 463, 464, 465, 466, 467, 468, 469, 470, 471, 472, 473, 474, 475, 476, 477, 478, 479, 480

Offset: 1

Author

M. F. Hasler, Nov 08 2023

Keywords

• nonn

Comments

These numbers come mostly in chunks/runs of length 2 or 36 or 23 (first occurring as length of the 7th run starting with 706) or later 14 (length of a run starting at 6768), 1081 (length of a run starting with 15303), 20 (length of a run starting with 21186), ...

The first isolated terms are a(2701) = 25595 and a(2702) = 25774.

This set exhibits an interesting self-similar, pseudo-symmetric structure. This is due to the following

Proposition: Let d(n) = (3^r(n)-1)/2 + (4^s(n)-1)/3, where r and s are exponents such that 4^(s(n)-1) <= 3^(r(n)-1) < 3^r(n) < 4^s(n), r(0) = s(0) = 1 being the only case with equality. Then any x <= d(n) is in this sequence iff d(n) - x is in the sequence.

The study of this set is certainly useful in view of a proof of Erdős's conjecture mentioned in A327621, namely, the positive density of A005836 + A000695 (set-wise sum). This is obviously equivalent to an asymptotic density strictly smaller than 1 of the present sequence which is the complement.

Examples

			0 is the empty sum, 1 = 3^0 = 4^0, 2 = 3^0 + 4^0 (*), 3 = 3^1, 4 = 4^1, 5 = 4^0 + 4^1, 6 = 3^0 + 4^0 + 4^1 (*), ..., so these numbers are not in this sequence.
After 61 = 3^0 + 3^1 + 3^2 + 3^3 + 4^0 + 4^1 + 4^2, the next larger number that is such a sum of powers is 64 = 4^3, which creates the first gap of [62, 63], first terms of this sequence.
		

Links

• Hugo Pfoertner, Table of n, a(n) for n = 1..20000

Crossrefs

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

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

Cf. A327621.

Programs

PARI

S34_upto(N)={my( p(N,b)=[b^k|k<-[0..logint(N,b)]] , S=[0] , i); for(b=3,4,
foreach(p(N,b),x, S = setunion(S, [x+y| y<-S[1 .. if( S[#S]+x < N, -1,
  i=setsearch(S,N-x,1), i-1, setsearch(S,N-x)) ]]))); S}
A367090_upto(N) = setminus([1..N], S34_upto(N)) \\ not very efficient...

Formula

Complement of A005836 + A000695 = { x+y ; x in A005836 and y in A000695 }.