[seqfan] Re: Nice nontrivial integer sequence

[Christian Sievers]

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();
}