VOOZH about

URL: https://oeis.org/A367090

⇱ A367090 - OEIS

login
A367090
Numbers that cannot be written as a sum of distinct powers of 3 and distinct powers of 4.
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
Thomas Bloom, Problem 125, Erdős Problems.
Erdős problems database contributors, Erdős problem database, see no. 125.
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...
(Python)
from itertools import count, islice
from gmpy2 import digits
def A367090_gen(startvalue=1): # generator of terms >= startvalue
for i in count(max(startvalue, 1)):
l = i.bit_length()+1>>1
for j in range(1<<l):
if '2' not in digits(i-int(bin(j)[2:], 4), 3):
break
else:
yield i
A367090_list = list(islice(A367090_gen(), 50)) # Chai Wah Wu, Sep 12 2025
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
KEYWORD
nonn
AUTHOR
M. F. Hasler, Nov 08 2023
STATUS
approved