[seqfan] Re: Nice nontrivial integer sequence

[Arthur O'Dwyer]

I confirm these results, using a C++ program that I wrote without looking
at Christian's C program. (Now I've looked, and I think we converged to the
same basic data structures... except that Christian doesn't even need to
store the list of `i` values? Ah, yes, now I see; that's clever. Updated
mine.)
https://quuxplusone.github.io/blog/2023/03/05/oeis-a360447/
has my C++ program and results up to a(96), at which point I, also, run out
of memory.

–Arthur

On Thu, Mar 2, 2023 at 7:15 AM Christian Sievers <seqfan at duvers.de> wrote:

> Hello,
>
> it seems like the list doesn't allow attachments, so I put (the latest
> version of) my program at the end of this mail.
>
> For the next billion terms I changed the type to unsigned integers.
> To go even further one could use (unsigned) *long* ints, but that's too
> much for my 32G memory.
>
> My only new results (still took only 48 seconds) are these:
>
> stable no. 96 is 1345208697 after 1708015633 terms
> 2 is at 4091
> after 2000000000 terms:
> 2 is at 4222
>
> All the best
> Christian
> ------------------------------------------------
>
> #include<stdio.h>
> #include<stdlib.h>
> #include<assert.h>
>
> #define N 2000000000
>
> typedef unsigned int T;
>
> T *next;
> T *sum;
>
> void update_sum(T n, T o){
>   T s, d, od, tp;
>   s = n+o;
>   d = (n>o) ? n-o : o-n;
>   tp=2*sum[s];
>   if(!tp){
>     sum[s]=n;
>     return;
>   }
>   od = (s>tp) ? s-tp : tp-s;
>   if (d<od)
>     sum[s]=n;
> }
>
> void report(T s, T i){
>   static T count=1;
>   printf("stable no. %u is %u after %u terms\n", ++count, s, i);
> }
>
> void report2(void){
>   T p,c;
>   p=c=1;
>   while(p!=2){
>     p=next[p];
>     ++c;
>   }
>   printf("2 is at %u\n", c);
> }
>
> int main(void){
>   T last,stable,need,i,p,q;
>   next=calloc(N+1u, sizeof(T));
>   assert(next);
>   sum=calloc(2u*N, sizeof(T));
>   assert(sum);
>   last=1;
>   stable=1;
>   need=5;
>   for(i=2; i<=N; ++i){
>     p=sum[i];
>     if(p){
>       q=next[p];
>       next[p]=i;
>       next[i]=q;
>       update_sum(p,i);
>       update_sum(i,q);
>       if (p==stable)
>         need=p+i;
>     } else {
>       next[last]=i;
>       update_sum(last,i);
>       last=i;
>     }
>     if (i==need){
>       while(i>=need){
>         stable=next[stable];
>         need=stable+next[stable];
>         report(stable,i);
>       }
>       report2();
>     }
>   }
>   printf("after %u terms:\n", N);
>   report2();
> }
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>