A367090 - OEIS

%I #20 Mar 24 2024 02:26:32

%S 62,63,143,144,207,208,209,210,211,212,213,214,215,216,217,218,219,

%T 220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,

%U 237,238,239,240,241,242,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480

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

%C 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), ...

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

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

%C 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.

%C 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.

%H Hugo Pfoertner, <a href="/A367090/b367090.txt">Table of n, a(n) for n = 1..20000</a>

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

%e 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.

%e 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.

%o (PARI) S34_upto(N)={my( p(N,b)=[b^k|k<-[0..logint(N,b)]] , S=[0] , i); for(b=3,4,

%o foreach(p(N,b),x, S = setunion(S, [x+y| y<-S[1 .. if( S[#S]+x < N, -1,

%o   i=setsearch(S,N-x,1), i-1, setsearch(S,N-x)) ]]))); S}

%o A367090_upto(N) = setminus([1..N], S34_upto(N)) \\ not very efficient...

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

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

%Y Cf. A327621.

%K nonn

%O 1,1

%A _M. F. Hasler_, Nov 08 2023