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

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.

Links

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

Formula

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

Example

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.

Prog

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

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.

Sequence in context: A003635 A188631 A076764 * A345496 A214251 A031058

Adjacent sequences: A367087 A367088 A367089 * A367091 A367092 A367093

Keyword

nonn

Author

M. F. Hasler, Nov 08 2023

Status

approved