Numbers that are not the sum of at most r+1 r-full numbers

[Elijah Beregovsky]

Erdős Problem #1107 conjectures every sufficiently large integer is a sum of r+1 r-full numbers. I’m trying to construct sequences for this problem. There’s already https://oeis.org/A056828 for the case r = 2 — numbers not representable as a sum of 3 or fewer squarefull numbers.

Analogous set for r = 3 seems to be

{5,6,7,12,13,14,15,20,21,22,23,31,38,39,46,47,53,58,69,77,79,85,95,101,103,111,175,196,212,228,231,247,327,444,458,490,606,662,860,975,1167,1470,1821,1967,2039}

There are no other terms < 84000 and I conjecture this is the full set.

For r=4 the sequence starts 

{6,7,8,9,10,11,12,13,14,15,21,22,23,24,25,26,27,28,29,30,31,37,38,39,40,41,42,43,44,45,46,47,52,53,……,29342,29551,29567,30463,30847,…}

after which my naive Mathematica program runs out of memory.

Are these sequences fine for OEIS, given they are likely fini and r=3 is probably full?

If the Erdős conjecture is true and all of these are indeed finite, there is also a very natural sequence “Largest number not representable as a sum of n+1 or fewer n-full numbers” which likely starts 119, 2039, >31000… What are the next elements? I don’t see any sequence in the encyclopaedia that matches this, but maybe there exists some reasonable formula?

Elijah

PS:

My program for r=3 is

n=41000;

t=Join[{0,1},Select[Range[2, n], Min[Table[# [[2]], {1}] & /@ FactorInteger[#]] > 2&]];

Complement[Range[n],Flatten[Outer[Plus,t,t,t,t]]]

To get the numbers for other r substitute r-1 for the red 2 and change the number of copies of t in the last line to r+1.

[Sean A. Irvine]

Hi Elijah,

Yes, these sequences are fine to add, even if finite.

Sean.

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/99C749D9-D6A0-4941-AD2C-AA50FB800DBE%40gmail.com.

[Robert Gerbicz]

For r=4 the last number could be 150271. My Pari-Gp code to print out all integers in [1,maxn] for that at most r+1 many r-powerful number is not enough:

f(r,maxn)={L=ceil(maxn^(1/r));a=vectorsmall(maxn);a[1]=1;
forprime(p=2,L,q=p^(r-1);while(q*p<=maxn,q*=p;
for(i=1,maxn\q,if(a[i]==1,a[i*q]=1))));
cnt=sum(i=1,maxn,a[i]);
v=vector(cnt);cnt=0;
for(i=1,maxn,if(a[i]==1,cnt+=1;v[cnt]=i));
for(k=2,r+1,forstep(i=maxn,1,-1,if(a[i]==0,for(j=1,cnt,if(i>v[j]&&a[i-v[j]]==1,a[i]=1;break())))));
for(i=1,maxn,if(a[i]==0,print1(i",")))}

--

[Elijah Beregovsky]

Thanks for the answers! I’ve started work on A392342 (r=3) and A392343 (r=4).

Elijah