If I had to guess, the operator approaches n^2 as n approaches infinity.

This isn't math, it's algorithms, but I think I figured out how to make my out-of-place hierarchysort cache-agnostic (e.g. L1 cache). Hierarchysort is a type of mergesort.

Original is here: https://github.com/mattrdowney/buoyancysort/blob/master/buoyancysort/out-of-place-hierarchysort.h

The basic idea is to have three interlaced lines (top, middle, bottom). When going forward the top and middle are used; when going backwards the bottom and middle are used.
...

...

You backtrack when you run out of elements to merge and act as if there are you are starting from scratch on the middle and bottom tracks going in the opposite direction. When you get to the end you should have double the space to the left by virtue of how things are set up.

If you did it naively you would still run out of space, which is why you need to start from the middle of the out-of-place auxilliary memory.

You basically zig-zag around the center, bigger & bigger.

I am basically positive this algorithm provides 1 fewer cache miss (at least ln(n) fewer) but I don't know if it works recursively properly because ideally it should provide 0 cache misses after the first cache line is read.

I'm wondering if you can do it with 3-4 Interlaced sequences or I'm making a logical mis-step.

You fundamentally need to have a bunch of detached tetris pieces and jam them together, and the question is: "Does the zig-zagging work / accumulate properly?"

I would think there's a mathematical way to map it with 4 Interlaced sequences and the concept of /ones' complement/ in binary. The forward direction is the normal unsigned binary string and the backwards direction is the ones' complement negative binary.

I am thinking of

{2, 3, 5, 7, 13, 17, 19... } -- https://oeis.org/A000043

And

{3, 5, 7, 11, 13, 17, 19, 23... } -- https://oeis.org/A000978

Particularly up to 24, which notably omit {11, 23} & {2}. The counts are 7 & 8 (total elements <= 23).

This makes me curious about:

https://oeis.org/A107360

Looking at

factor {2, 4, 6, 12, 16, 18, 30, 60, 126}

There's:

1 power of 7
2 powers of 5
6 powers of 3
9 powers of 2

Which I was mostly curious about because 1 = 1!, 2 = 2!, 6 = 3!

Which would imply something like 3.31209... based on the solution to gamma(n+1) = 9

π root of 63 x^3 + 824 x^2 - 4398 x + 3647 near x = 1.05427≈3.3120972978664913634

Seems relevant to me

Or at least interesting.

Also, based on the 41st Mersenne and Wagstaff exponents, I wonder if the ratio of these series is asymptotically 6:

24036583/4031399 ~= 6

Actually, wait, the 30th values are nowhere near 6:

132,049÷42,737 ~= 3

The ratios themselves are interesting:

{2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203}/{3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191}

The first 4 are less than 1
The next 3 are equal to 1
The next 5 are between 1 and 89/43
The rest seem larger so far.

This leads to the observation that 89/43 = (8*11+1)/(4*11-1)

Which then made me think about Heegner numbers and {5,29,139,197}.

197 - 16*11 = 21 ~= 22
16*11 - 137 = 37
197 - 137 = 58

a la the "class 2 Heegner numbers"

I think the first four Wagstaff primes are the most interesting:

3, 11, 43, 683...

3 = Heegner[3]
11 = Heegner[5]
43 = Heegner[7]
683 = (Ibrishimova[9]-1)/2

I don't know if I mentioned I read this a week or so ago:

https://en.m.wikipedia.org/wiki/Mersenne_conjectures#New_Mersenne_conjecture

It's certainly interesting.

I didn't even realize I subconsciously re-found something I read:

https://en.m.wikipedia.org/wiki/Mersenne_conjectures#New_Mersenne_conjecture

And

https://oeis.org/A107360

{3, 5, 7, 13, 17, 19, 31, 61, 127}^2 - 6

The first 5 are prime, which I imagine would relate to the Fermat primes:

3 <-> 3
19 <-> 5
43 <-> 17
163 <-> 257
283 <-> 65537

This leaves

{3, 19, 43, 163, 283, 355, 955, 3715, 16123}

Multiples of 5: {71,191,743}
Multiple of 23: {701}

pi function({3,19,43,163,283,71,191,743,701})

-->

{2, 8, 14, 38, 61, 20, 43, 132, 126}

Which made me look at

2657 = (15/4)*prime(2^7 - 1) - 7/4

pi function({3,19,43,163,283,71,191,743,701})

-->

{2, 8, 14, 38, 61, 20, 43, 132, 126}

~=

{1, 9, 16, 36, 58, 22, 37, 127, 127}

sqrt(pi function({1,2,3,7,11,19,43,67,163}))

-->

{0, 1, 1.41421, 2, 2.23607, 2.82843, 3.74166, 4.3589, 6.16441}

Which may imply 1, 2, and 7 are special.

I have a theory that

2657/prime(7^2-7/4) ~= 12

When extrapolating / interpolating

Oh, cool, I forgot this is essentially solvable and I'm correct- ish:

2657/prime(7^2-7/4) ~= 12

prime(7^2-7/4) ~= 2657/12

7^2-7/4 ~= pi function(2657/12)

And

7^2-2 = pi function(2657/12)

prime(23)*x = 2657

--> x~=32

prime(24)*x = 2657

--> x~=30

The prior was based on:

(3^2-1) = pi function(2657/120)
(7^2-2) = pi function(2657/12)

And made me curious about

15 = 3*5
31 ~= 3^(3/2)*6
63 = 3^2*7

sqrt(pi function({1,2,3,7,11,19,43,67,163}))

-->

{0, 1, sqrt(2), 2, sqrt(5), sqrt(8), sqrt(14), sqrt(19), sqrt(38)}

{0, 1, 2}

sqrt({5, 8}) --> 4 + 1, 9 - 1; (8 - 5) + 1 = 4, (8 + 5) + 3 = 16

sqrt({2, 19}) --> ?

sqrt({14, 38}) --> 16 - 2, 36 + 2; (38 - 14) + 1 = 25, (38 + 14) - 3 = 49

2+19 = 22 - 1
2*19 = 37 + 1
2<*>19 ?= 58 // can't find an operator

19*2^e ~= 5^3
19*2^pi ~= 13^2

(19*2^pi - 13^2)/(19*2^e - 5^3) ~= -36

This made me curious about:

(7)^(23/9) ~= 12^2

Which has interesting complex roots as well.

I just realized

19*2^((e+pi)/2) ~= 144.79...
19*2^((e*pi)^.5) ~= 144.02...

So it checks out pretty well with the previous idea.

sqrt(144.5*2) = 17

(19^2 + 2)/3 = 11^2
(12^2 + 1/2)*2 = 17^2

Which I'm gonna try to relate back to 12 & 19 in music theory.

((15.5^2)*(2/3))-14^2 ~= -36

(36 - (19*2^pi - 13^2)/(19*2^e - 5^3))/6 ~= 12

2657 = 2000*2^(-e + π) - 5^2

19*2^2.6854520010653064453097 ~= 122.2236...
19*2^3.2758229187218111597876 ~= 184.0240...

https://en.m.wikipedia.org/wiki/Khinchin%27s_constant
https://en.m.wikipedia.org/wiki/L%C3%A9vy%27s_constant

For the above, the values are essentially 11^2 + epsilon & (17/2)^2 + epsilon, which sort of relates back to:

(19^2 + 2)/3 = 11^2
(12^2 + 1/2)*2 = 17^2