Ancestors

Toot

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

Descendants

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

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: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 groff on 2024-12-31 at 17:29

[#]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:29

I ran @geoffl's program and got this.

Source: https://bbcmic.ro/?t=bfEME #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%;

N.

=> 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%;

N.

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

Written by BBC Micro Bot :mastodon: on 2025-01-01 at 01:23

I ran @geoffl's program and got this.

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

=> View attached media

=> More informations about this toot | More toots from bbcmicrobot@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

Written by groff on 2025-01-01 at 02:10

@rheolism

[#]bbcmicrobot MO.0:MO.7:N%=1E4:B%=&3000:@%=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%;

N.

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

Written by BBC Micro Bot :mastodon: on 2025-01-01 at 02:11

I ran @geoffl's program and got this.

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

=> View attached media

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

Written by Rheolism on 2025-01-01 at 03:36

@geoffl #bbcmicrobot MO.0:V.22,7:N%=1E4:@%=5:P.'"Numbers that are the sum of two squares"

F.X%=0TOSQRN%:S%=X%*X%:F.Y%=0TOX%:A%=S%+Y%*Y%:IFA%<N%A%?H.=TRUE:N.,EL.N.X%

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

N.

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

Written by BBC Micro Bot :mastodon: on 2025-01-01 at 03:36

I ran @rheolism's program and got this.

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

=> View attached media

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

Written by groff on 2025-01-01 at 17:24

@rheolism

[#]bbcmicrobot MO.0:V.22,4:N%=1E4:@%=5:P.'"Numbers that are the sum of two squares (by two or more different methods)."

F.X%=0TOSQRN%:S%=X%*X%:F.Y%=0TOX%:A%=S%+Y%*Y%:IFA%<N%A%?H.=-NOTA%?H.:N.,EL.N.X%

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

N.

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

Written by BBC Micro Bot :mastodon: on 2025-01-01 at 17:25

I ran @geoffl's program and got this.

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

=> View attached media

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

Written by Rheolism on 2025-01-01 at 19:41

[#]bbcmicrobot MO.0:V.22,7:w=!-52:F.O=0TO2S.2:P%=@%:[OPTO

SED

.l

LDA H.,X

BEQn

CLD

STX81

LDA#32

JSRw

TAX

LDA80

LSRA:LSRA:LSRA:LSRA

BEQz0

ORA#48:JSRw:LDX#48

BNEZ0

.z0:TXA:JSRw:.Z0

LDA80

AND#15

BEQz1

ORA#48:JSRw

BNEZ1

.z1:TXA:JSRw:.Z1

TYA

LSRA:LSRA:LSRA:LSRA

BEQz2

ORA#48:JSRw:LDX#48

BNEZ2

.z2:TXA:JSRw:.Z2

TYA

AND#15

ORA#48:JSRw

LDX81

SED

.n

TYA

CLC

ADC#1

TAY

BCCc

LDA80

ADC#0

BCSz

STA80

.c

INX

BNEl

INCl+2

BPLl

.z

CLD

RTS

]:N.

N%=1E4:P.'"Numbers that are the sum of two squares"

F.U%=0TOSQRN%:S%=U%*U%:F.V%=0TOU%:A%=S%+V%*V%:IFA%<N%A%?H.=TRUE:N.,EL.N.U%

CA.@%

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

Written by BBC Micro Bot :mastodon: on 2025-01-01 at 19:41

I ran @rheolism's program and got this.

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

=> View attached media

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

Written by Rheolism on 2025-01-01 at 19:46

@bbcmicrobot The assembler printing loop increments a BCD counter as well as the binary counter for checking the array of flags so printing the value out is much simpler as each decimal digit is its own nibble. Handily (for doing this at least) INC/INX/etc ignore BCD mode so we only need to turn off BCD mode to call into the OS to write out characters.

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

Written by Rheolism on 2025-01-02 at 01:11

[#]bbcmicrobot MO.0:V.-233;96,144,32,64,240;0;22,6:N%=12288:@%=0:F.U%=1TOSQRN%:S%=U%*U%:IFS%?H. T%=S%?H.:P.TAB(H%)S%?(H.-T%*T%)"ÿ+"T%"ÿ="U%"ÿ";:H%=(H%+13)MOD39:IF0EL.S%?H.=U%:F.V%=1TOU%:A%=S%+V%*V%:IFA%<N%A%?H.=U%:N.,EL.N.U%:P.

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

Written by groff on 2025-01-18 at 10:44

[#]bbcmicrobot 🚀 MO.1:V.5

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

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

MOVE460,760

REP.L=1+L

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

GC.0,1+(R/2)MOD4

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

U.L>2^15

V.1

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

Written by BBC Micro Bot :mastodon: on 2025-01-18 at 10:44

I ran @geoffl's program and got this.

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

=> View attached media

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

Written by groff on 2025-01-18 at 10:45

@bbcmicrobot Unnecessary MOD4 in the GCOL.

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

Written by groff on 2025-01-18 at 11:17

[#]bbcmicrobot 🚀 MO.1:V.5

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

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

MOVE460,760

REP.L=1+L

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

GC.0,.1+(R/4)

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

U.L>2^15

V.1

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

Written by BBC Micro Bot :mastodon: on 2025-01-18 at 11:18

I ran @geoffl's program and got this.

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

=> View attached media

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

Written by groff on 2025-01-20 at 21:49

I don't want to keep spamming the @bbcmicrobot with Dragon Curves so here's a one liner that anyone can run if they feel like it.

MO.0:MOVE460,780:REP.L=-NOTL:T=L:REP.T=T/2:U.T>INTT:D=((1ANDT)2-NOTD)MOD4:PL.65,2((D=3)-(D=1)),2*((D=0)-(D=2)):U.L>2^17:VDU5,1

It calculates the turns in order by taking the bit to the left of the least significant 1 in the binary expansion of a counter. If it's 0 turn right else turn left.

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