Ancestors

Written by groff on 2024-12-28 at 15:10

Fiddling around with some recursion and the dragon curve and what should pop out but this exact sequence.

https://oeis.org/A072339

While it wasn't at all obvious to me that it would match a sequence like this, it is easy to demonstrate the connection. Take the odd numbers and use them as right turns and the even numbers as left turns.

Shame I don't have access to Knuth's work to see if the connection is described there.

@Unprovable

=> More informations about this toot | More toots from geoffl@mastodon.me.uk

Written by groff on 2024-12-28 at 15:31

Going from the dragon curve to that sequence is slightly more tricky but only involves counting the number of times a turn is flipped left/right or right/left at each iteration.

=> More informations about this toot | More toots from geoffl@mastodon.me.uk

Written by groff on 2024-12-28 at 18:47

Maybe he didn't. :)

https://youtu.be/v678Em6qyzk

=> More informations about this toot | More toots from geoffl@mastodon.me.uk

Written by groff on 2024-12-29 at 02:32

[#]bbcmicrobot 🚀MO.0:GC.3,1

P."Any number n can be written in the form n = 2^k1 - 2^k2 + 2^k3 - ... + 2^kx"'"where the signs alternate and k1 > k2 > k3 > ... >kx >= 0."'"E.G. a(6)=2 since 6=2^3-2^1. Sequence gives the minimal value of x."

V.28,59,12,79,4

DIMX(3),Y(3):D=0

X(0)=4:X(2)=-4:Y(1)=4:Y(3)=-4

MOVE359,719

REP.L=1+L

PL.1,X(D),Y(D)

N=L:T=N:C=0:R=1:Z=1

REP.T=T/2:C=C+1:U.T<=1

M=2^(C-1):E=2^C

REP.

IFN>M ANDN<E R=R+1:Z=2EORZ:N=E-N

E=E/2:M=M/2:U.M<2

D=(D+Z)MOD4

P.';"a("L") = "R;

U.0

=> More informations about this toot | More toots from geoffl@mastodon.me.uk

Written by BBC Micro Bot :mastodon: on 2024-12-29 at 02:32

I ran @geoffl's program and got this.

Source: https://bbcmic.ro/?t=beHPj #bbcbasic

=> View attached media

=> More informations about this toot | More toots from bbcmicrobot@mastodon.me.uk

Written by groff on 2024-12-29 at 02:34

[#]bbcmicrobot 🎬MO.0:GC.3,1

V.28,59,12,79,4

DIMX(3),Y(3):D=0

X(0)=4:X(2)=-4:Y(1)=4:Y(3)=-4

MOVE359,719

REP.L=1+L

PL.1,X(D),Y(D)

N=L:T=N:C=0:R=1:Z=1

REP.T=T/2:C=C+1:U.T<=1

M=2^(C-1):E=2^C

REP.

IFN>M ANDN<E R=R+1:Z=2EORZ:N=E-N

E=E/2:M=M/2:U.M<2

D=(D+Z)MOD4

P.';"a("L") = "R;

U.0

=> More informations about this toot | More toots from geoffl@mastodon.me.uk

Written by BBC Micro Bot :mastodon: on 2024-12-29 at 02:35

I ran @geoffl's program and got this.

Source: https://bbcmic.ro/?t=beHRB #bbcbasic

=> View attached media

=> More informations about this toot | More toots from bbcmicrobot@mastodon.me.uk

Written by groff on 2024-12-29 at 02:45

@bbcmicrobot This is an easier, faster, and less memory intensive method to generate the same sequence than the code at https://oeis.org/A072339

It also generates the dragon curve as a side effect.

=> More informations about this toot | More toots from geoffl@mastodon.me.uk

Written by groff on 2024-12-31 at 17:15

[#]bbcmicrobot MO.1:@%=8:X=0:Y=1:P.'"Numbers that are the sum of two squares"'X;:REP.L=XX+YY:R=L*2+1:Q%=1+SQRL:P.L;:F.E%=1TOQ%:F.F%=Q%-E% TOQ%-(E%/3):T=E%*E%+F%*F%:IFT>L ANDT<R R=T:U=E%:V=F%

N.,:X=U:Y=V:U.0

=> More informations about this toot | More toots from geoffl@mastodon.me.uk

Written by BBC Micro Bot :mastodon: on 2024-12-31 at 17:16

I ran @geoffl's program and got this.

Source: https://bbcmic.ro/?t=bfEzt #bbcbasic

=> View attached media

=> More informations about this toot | More toots from bbcmicrobot@mastodon.me.uk

Written by Rheolism on 2024-12-31 at 19:23

[#]bbcmicrobot @geoffl CLS:N%=1E4:DIMB%N%:@%=5:P.'"Numbers that are the sum of two squares"

F.X%=0TOSQRN%:T%=0:F.Y%=0TOX%:A%=S%+T%:IFA%<N%A%?B%=1:T%=T%+Y%-NOTY%:N.EL.Y%=X%:N.

S%=S%+X%-NOTX%:N.

F.L%=0TON%-1:IFL%?B%=1P.L%;

=> More informations about this toot | More toots from rheolism@oldbytes.space

Written by BBC Micro Bot :mastodon: on 2024-12-31 at 19:23

I ran @rheolism's program and got this.

Source: https://bbcmic.ro/?t=bfGyW #bbcbasic

=> View attached media

=> More informations about this toot | More toots from bbcmicrobot@mastodon.me.uk

Written by Rheolism on 2024-12-31 at 20:01

@bbcmicrobot The runtime here is (just) dominated by printing the answers - this completes in 44.50 seconds, but removing that PRINT it only takes 22.19.

=> More informations about this toot | More toots from rheolism@oldbytes.space

Written by groff on 2025-01-01 at 01:22

@rheolism #bbcmicrobot CLS:N%=1E4:DIMB%N%:@%=5:P.'"Numbers that are the sum of two squares"

F.X%=0TOSQRN%:T%=0:F.Y%=0TOX%:A%=S%+T%:IFA%<N%A%?B%=-1:T%=T%+Y%-NOTY%:N.EL.Y%=X%:N.

S%=S%+X%-NOTX%:N.

F.L%=B%TOB%+N%-1:IF?L%P.L%-B%;

=> More informations about this toot | More toots from geoffl@mastodon.me.uk

Written by groff on 2025-01-01 at 01:31

@rheolism

Nice algorythm.

Setting the memory locations to -1 makes the last IF quicker as it's implicit true rather than =0, and as there are more misses than hits adding B% to the loop then subtracting it from the number printed is faster than adding B% to every lookup. Saving about 2.34 seconds.

Edit: Oops, that introduces an error that prints several false positives. Too tired to work out why right now.

Edit 2: The memory on tbe beeb isn"t initialised fully empty. Thats why.

=> More informations about this toot | More toots from geoffl@mastodon.me.uk