Electrons bouncing in a wire

2 2
4 6
6 14
8 14
10 62
12 126
14 30
16 30
18 1022
20 126
22 4094
24 2046
26 1022
28 32766
30 62
32 62
34 8190
36 174762
38 8190
40 2046
42 254
44 8190
46 16777214
48 4194302
50 510
52 134217726
54 2097150
56 1022
58 1073741822
60 2147483646
62 126
64 126
66
68 8388606
70
72 1022
74 2097150
76
78
80
82
84 510
86
88 4094
90 8190
92 2046
100
126 254

orlp

We do.

You haven't proven your conjectured formula.

Remember how everything seemed to have nice formulas, and then n = 36 came along?

somebody

well, it's applying for all of them

test n=73

orlp

Law of big numbers, mate.

If 36 is weird, perhaps other numbers are as well

somebody

yeah

also, i didn't prove it

someone else did

wait a sec

in The Nineteenth Byte, 10 hours ago, by PhiNotPi

It's the same rule, inside of itself.

(click the link)

somebody

1:41 PM

:( one at 10b, one at 12b

orlp

up to 128

gist.github.com/orlp/038d52384a8f377808cb

oeis.org/A160657

somebody

i'll have a few running overnight/tomorrow and see if i can get any more results

orlp

matches so good

except for n = 36

n=36 is so damn mysterious

somebody

n=36 is that divided by 3

for some reason the period is three times shorter than it is on that sequencs

also, you can pretty much write a faster one already that is mostly correct

maybe you could try verifying A160657 for the 18th term

rule is more complicated: born if 3/6 neighbours, survives if 1/2/5 neighbours

wait

nathanieljohnston.com/2009/05/…

same patern

*pattern

t turns out that these oscillators are, in a sense, emulating the “Rule 90” 1D cellular automaton

^- A160657 needs to be fixed

also, it needs a new definition

in the comments is the f(2n+1)=2f(n)

orlp

2:07 PM

Going to make a faster calculator

template<unsigned N>
void next(uint64_t* v) {
    constexpr unsigned words = N / 64;
    constexpr unsigned bits_in_last_word = N % 64;
    constexpr uint64_t mask =
        bits_in_last_word == 0 ? uint64_t(-1) :
        (uint64_t(1) << (bits_in_last_word)) - 1;

    uint64_t last_hi = 0;
    for (unsigned i = 0; i < words; ++i) {
        uint64_t next_lo = v[i + 1] << 63;
        uint64_t new_last_hi = v[i] >> 63;
        v[i] = (v[i] << 1) ^ (v[i] >> 1) ^ next_lo ^ last_hi;
        last_hi = new_last_hi;

The complicated part is done

Except that's incorrect .

for (unsigned i = 0; i < words; ++i) { should be for (unsigned i = 0; i < words - 1; ++i) {

somebody

++i?

orlp

hrm?

somebody

why not i=1 then i++?

wait, nvm

wait, why not?

um

orlp

for (a; b; c) { d } is the same as a; while (b) { d; c; }

somebody

also does template work like that?

orlp

2:16 PM

i++ here is the exact same as ++i

The reason it's a template is because it allows the compiler to do all the constant computation at compile-time

since N will be known at compile-time, because it's a template parameter

so the loop gets unrolled, etc

oh found another mistake

somebody

also, why uint64_t?

are we not gonna go over 128?

orlp

@somebody do you have a 128 bit CPU?

somebody

no

orlp

then why use 128 bit words :)

64 bit words perfectly fit into 1 register

somebody

but what if it goes over 2^64-1?

orlp

2:22 PM

then it will use two words

somebody

oh

i dont get how the remplate is supposed to work

nvm

uh

still don't get how it's supposed to work

how do you pass in 'n' at compile time?

orlp

next<120>(v)

somebody

2:41 PM

:( not even 100, and they're over 17b

PhiNotPi

hello

somebody

@orlp don't think constexpr works that way

orlp

@somebody template arguments are always known at compile time

somebody

and haven't seen template used that way

yeah, but all the constexpr examples i've seen are functions

nvm

PhiNotPi

So, we have the series 1,2,3,3,5,6,4...

somebody

2:49 PM

?

you mean oeis.org/A003558 ?

PhiNotPi

Yes

somebody

also, scroll up, oeis.org/A160657 is the same as even number of this

@PhiNotPi what about the series?

PhiNotPi

And f(2n) = 2 * (2^a(n) - 1) / k

somebody

also on the website linked above somewhere (in the comments, and kinda)

@PhiNotPi that pretty much means we can predict it, just need to figure out whyn=36 is weird

PhiNotPi

If a(n) is a composite number, xy (for some values of x and y)

somebody

2:53 PM

and home there is only one kind of weird outlier thing (i.e. the n=36 family)

PhiNotPi

Then f(2n) = 2 * (2^a(n) - 1) / k = 2 * (2^x-1)*(2^y-1) / k

somebody

*hope

PhiNotPi

Since the period is always an integer, we only have to worry about weird divisors when a(n) is a composite number

somebody

you mean even?

well, for the first one

weird divisors apply to 36, 73, 147 etc

well, good night, gonna leave 94 and 70 running overnight

PhiNotPi

For 36, f(18) = 18 = 2 * 3 * 3, the 2 allows it to have a wierd divisor

since 2^2-1 = 3, the value of 2^18-1 is divisible by 3

@somebody I don't think you were understanding me properly.

brb

somebody

3:23 PM

well, i know 36 is weird, and therefore 2*36+1 etc, but i didn't know why

PhiNotPi

@somebody Look at this chat.stackexchange.com/transcript/message/27564509#27564509

somebody

yeah

but what has it got to do with 35?

*36

PhiNotPi

It explains why 2*36+1 is weird

somebody

yeah, i know, i saw that when you posted it

PhiNotPi

okay

somebody

3:26 PM

but that doesn't explain why 36 is weird in the first place

idk if there's anything weird with row 36 of sierpinski's gasket

maybe it has three parts or something?

or maybe it's to do with pascal's triangle row 36

PhiNotPi

@somebody Impossible

Right now I'm trying to figure out the connection between the A003558 sequence and the numbers

> Least number m such that 2^m == +- 1 (mod 2n + 1)

2^m - 1 == 0 (mod 2n + 1)

^ that's one of the two branches of the formula

but 2^m-1 is equal to 1/2 the cycle length

so maybe we can fill in...

generation/2 == 0 (mod 2n + 1)

somebody

?

PhiNotPi

That's from the sequence definition on OEIS

somebody

well, A160657 is every even term (except 36), odd terms can be found from the even ones, with the exception of the ones that die out

nathanieljohnston.com/2009/05/…

it says that it kinda simulates rule 90

PhiNotPi

I'm working on A003558 right now

generation/2 == -2 (mod 2n + 1) is the other branch

Then we end up with one of the two congruences...

generation/2 == 0 (mod width + 1)

generation/2 == -2 (mod width + 1)

For width = 4, it turn out the the second one is correct, since 6/2 == -2 mod 5

where 6 is the number of generations

orlp

3:46 PM

ok, got a new fast program to compute electron numbers

PhiNotPi

cool

orlp

gist.githubusercontent.com/orlp/8cee51250cfed6b713fd/raw/…

compile with g++ -O2 -m64 -march=native -std=c++11 electron.cpp

somebody

but you don't use argc

orlp

correct

N needs to be known at compile time

so you edit the source :)

somebody

oh

orlp

3:51 PM

(this is so the compiler can optimize everything to the max)

so, let's see if we can crack 66

somebody

*you?

orlp

oh

PhiNotPi

2^34-2 is the predicted length

orlp

lol

only took 57 seconds

somebody

D:

orlp

3:53 PM

66 17179869182

somebody

66 is near max as well

also, why is your computer so fast?

orlp

the program is fast

PhiNotPi

Yep, it's 2^34-2

orlp

and my computer is just an i5 2600k or smt

i5-4670k

sorry

so pretty damn fast

somebody

but...

orlp

3:55 PM

welcome to C++ :P

somebody

my laptop is way slower

orlp

pypy is good, but not that good

did you compile with the right flags btw?

somebody

yeah

wonder how long it would take for your computer to do n=100

orlp

4:07 PM

70 68719476734

seems like we've got a ton of 'busy beaver's

PhiNotPi

2^36 - 2 fits the pattern

orlp

is there a conjecture for even numbers?

excluding n=36

everything except n = 36 fits?

somebody

oeis.org/A160657

orlp

all other terms fit?

somebody

yes

atm

PhiNotPi

4:13 PM

I would actually say oeis.org/A003558 is the best sequence to look at

with f(2n) = 2 * (2^a(n) - 1)

Maybe we can try checking 100 or 196 for weirdness?

somebody

/me starts waiting

um

PhiNotPi

100 might not terminate in any reasonable period of time

somebody

for me

but i can wait overnight

PhiNotPi

for anybody

2^51 - 2 is a long time

It'll take about 32768 times as long as 70

somebody

assuming it reaches the limit

PhiNotPi

4:24 PM

which it probably will

somebody

:(

PhiNotPi

if 70 took a minute, 100 might take over 20 days

somebody

we need to start a BOINC project :P

it's may be faster to use hashlife to 2^51 -2, then go backwards 2, 4, etc. iterations

orlp

5:44 PM

78 1099511627774

confirmed

PhiNotPi

I'm not sure if that fits the pattern or not

Actually, yeah it does

What even numbers are we still missing?

El'endia Starman

6:02 PM

You guys have really taken this and run it with. I love it. :D

somebody

8:42 PM

82, 94, 100

El'endia Starman

@orlp 121 still has a ? next to it.

somebody

:( doesn't look like 100 is gonna finish any time within this month

@orlp you forgot to add 78

to the gist

orlp

9:41 PM

70 68719476734
78 1099511627774
82 4398046511102
94 45812984490

dat 94 though

OOOOOOOOOOH

94 is another one

0b101010101010101010101010101010101010

El'endia Starman

OOOH.

94 = 2*47. ?????????

Well, there go all those theories!

And now, instead of one mystery, we have two mysteries. Which, actually, I kinda like more than just having one, because now we have more data. :P

orlp

dno

wouldn't it be really mysterious if only n = 36 was odd/

El'endia Starman

Quite.

@orlp ?