[seqfan] Re: Nice nontrivial integer sequence
Brendan McKay
brendan.mckay at anu.edu.au
Mon Mar 6 05:35:19 CET 2023
Without understanding a thing, I defined T as "unsigned long long",
N as "5000000000ULL" and changed "%u" to "%llu%. Then I ran it
on a computer with 128GB. It took 12 minutes. Here is all the output.
It looks like it isn't much use??
Brendan
-------------------------------------------------------------------------------------------
stable no. 2 is 4 after 5 terms
2 is at 5
stable no. 3 is 11 after 15 terms
2 is at 10
stable no. 4 is 29 after 40 terms
2 is at 17
stable no. 5 is 47 after 76 terms
stable no. 6 is 18 after 76 terms
2 is at 25
stable no. 7 is 61 after 79 terms
2 is at 25
stable no. 8 is 165 after 226 terms
2 is at 39
stable no. 9 is 434 after 599 terms
2 is at 57
stable no. 10 is 703 after 1137 terms
2 is at 74
stable no. 11 is 1675 after 2378 terms
2 is at 96
stable no. 12 is 972 after 2647 terms
2 is at 102
stable no. 13 is 2213 after 3185 terms
2 is at 106
stable no. 14 is 10093 after 12306 terms
2 is at 176
stable no. 15 is 17973 after 28066 terms
2 is at 234
stable no. 16 is 25853 after 43826 terms
2 is at 268
stable no. 17 is 59586 after 85439 terms
2 is at 331
stable no. 18 is 33733 after 93319 terms
stable no. 19 is 7880 after 93319 terms
stable no. 20 is 21427 after 93319 terms
stable no. 21 is 56401 after 93319 terms
2 is at 341
stable no. 22 is 204177 after 260578 terms
2 is at 475
stable no. 23 is 147776 after 351953 terms
stable no. 24 is 91375 after 351953 terms
stable no. 25 is 217724 after 351953 terms
stable no. 26 is 126349 after 351953 terms
2 is at 513
stable no. 27 is 414021 after 540370 terms
2 is at 574
stable no. 28 is 287672 after 701693 terms
stable no. 29 is 161323 after 701693 terms
stable no. 30 is 34974 after 701693 terms
stable no. 31 is 48521 after 701693 terms
stable no. 32 is 13547 after 701693 terms
stable no. 33 is 5667 after 701693 terms
stable no. 34 is 9121 after 701693 terms
stable no. 35 is 12575 after 701693 terms
stable no. 36 is 28604 after 701693 terms
stable no. 37 is 16029 after 701693 terms
stable no. 38 is 3454 after 701693 terms
stable no. 39 is 1241 after 701693 terms
stable no. 40 is 269 after 701693 terms
stable no. 41 is 1180 after 701693 terms
stable no. 42 is 3271 after 701693 terms
stable no. 43 is 2091 after 701693 terms
stable no. 44 is 911 after 701693 terms
stable no. 45 is 2464 after 701693 terms
stable no. 46 is 11409 after 701693 terms
stable no. 47 is 20354 after 701693 terms
stable no. 48 is 90361 after 701693 terms
stable no. 49 is 250729 after 701693 terms
stable no. 50 is 160368 after 701693 terms
2 is at 622
stable no. 51 is 551111 after 711479 terms
2 is at 624
stable no. 52 is 1492965 after 2044076 terms
2 is at 825
stable no. 53 is 941854 after 2434819 terms
stable no. 54 is 390743 after 2434819 terms
stable no. 55 is 1011861 after 2434819 terms
stable no. 56 is 621118 after 2434819 terms
2 is at 873
stable no. 57 is 2714847 after 3335965 terms
2 is at 955
stable no. 58 is 15667964 after 18382811 terms
2 is at 1490
stable no. 59 is 44289045 after 59957009 terms
2 is at 1969
stable no. 60 is 161488216 after 205777261 terms
2 is at 2599
stable no. 61 is 278687387 after 440175603 terms
stable no. 62 is 117199171 after 440175603 terms
stable no. 63 is 72910126 after 440175603 terms
stable no. 64 is 174441333 after 440175603 terms
2 is at 3074
stable no. 65 is 450413873 after 624855206 terms
2 is at 3311
stable no. 66 is 275972540 after 726386413 terms
stable no. 67 is 101531207 after 726386413 terms
stable no. 68 is 28621081 after 726386413 terms
stable no. 69 is 12953117 after 726386413 terms
stable no. 70 is 36144504 after 726386413 terms
stable no. 71 is 23191387 after 726386413 terms
stable no. 72 is 33429657 after 726386413 terms
stable no. 73 is 10238270 after 726386413 terms
stable no. 74 is 7523423 after 726386413 terms
stable no. 75 is 19855422 after 726386413 terms
stable no. 76 is 52042843 after 726386413 terms
stable no. 77 is 32187421 after 726386413 terms
stable no. 78 is 44519420 after 726386413 terms
stable no. 79 is 12331999 after 726386413 terms
stable no. 80 is 4808576 after 726386413 terms
stable no. 81 is 21328033 after 726386413 terms
stable no. 82 is 59175523 after 726386413 terms
stable no. 83 is 156198536 after 726386413 terms
stable no. 84 is 253221549 after 726386413 terms
stable no. 85 is 350244562 after 726386413 terms
stable no. 86 is 97023013 after 726386413 terms
stable no. 87 is 231893516 after 726386413 terms
stable no. 88 is 134870503 after 726386413 terms
stable no. 89 is 37847490 after 726386413 terms
stable no. 90 is 16519457 after 726386413 terms
stable no. 91 is 61269252 after 726386413 terms
stable no. 92 is 167288299 after 726386413 terms
stable no. 93 is 273307346 after 726386413 terms
stable no. 94 is 106019047 after 726386413 terms
stable no. 95 is 362806936 after 726386413 terms
2 is at 3416
stable no. 96 is 1345208697 after 1708015633 terms
2 is at 4091
after 5000000000 terms:
2 is at 5140
On 3/6/23 09:27, Arthur O'Dwyer wrote:
> 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/
>>
> --
> Seqfan Mailing list -http://list.seqfan.eu/
More information about the SeqFan
mailing list