Matt Downey @SciFiGameDev@mastodon.gamedev.place

Finished my 6-second game trailer for my Asteroids (1979)-clone in virtual reality:

https://youtu.be/tGoc2T6ABUc

I think this might be better:

1,
4, //1*2^2
12, //4*3
28, // 4*7
60, // 12*5
156, // 12*13
308, // 28*11
868, // 28*31
1740, // 60*29
4380, // 60*73
11076, // 156*71
28236, // 156*181
55132, // 308*179
142604, // 308*463
400148, // 868*461

Here's another attempt at beating Ciura using sprawling prime numbers:

1,
4, //1*2^2
12, //4*3
28, // 4*7
60, // 12*5
132, // 12*11
364, // 28*13
868, // 28*31
1740, // 60*29
4020, // 60*67

Maclaurin series of n^n:

f(0) + f'(0)*x + f''(0)*x^2/2 + f'''(0)*x^3/6 + f''''(0)*x^4/24 + f'''''(0)*x^5/120 + f''''''(0)*x^6/720 + f'''''''(0)*x^7/5040

0^0 (1, e.g. use the limit) + [n*n^(n-1)]*n + [n^n]*n^2/2 + [n^n]*n^3/6 + ... (giving up here)

Interestingly, n! doesn't grow fast enough (at all).

I might try to find the Maclaurin (Taylor) series of n^n and try to reverse engineer the inverse of n^n.

The reason I got started on this idea was the concept of using a Taylor series for lg(v)/lg(n) and v^(1/n), but that isn't going to work most likely because Taylor series seem to take a single variable.

A interesting idea:

(n + lg(v)/lg(n) + v^(1/n))/3, v=27, n=2.91

Here I'm using three functions to try to get a good average. The graph looks really smooth compared to several alternatives in Wolfram Alpha.

I'll try to incorporate Simpson's rule here.

Ehh, but even implicit Euler doesn't converge that fast:

(y^(1/n)-n)/2+n, y=2, n=1.56315

I think I might need Simpson's rule or something similar.

I forgot about implicit Euler's method. That's probably what I'll do.

I'm sort of curious how you might speed up convergence using non-mathematical techniques (although this is sort of statistical to be fair).

Try to compute values n0 to n99

Compute approximate n0,
Using n_i approximate n_i+1 (only one iteration) i=1 to 99.
Knowing the data is monotonically increasing, average neighboring values that are inverted.
Smooth out / massage the data based on the rate of change.
Repeat until happy with results.

Since you would be performing this operation in a Sacks spiral, you could use the exact value of the previous element as an estimate.

Speeding up the rate of convergence would be nice, but it's been a while since I got an F in Applied Numerical Methods XD

I'm also sort of curious about http://oeis.org/A085892

I found it because I was thinking about how to calculate the inverse of n^n on my own.

My thought process was to first approximate using n! (by using a cross between gallop mode division and https://www.cs.cmu.edu/~cburch/survey/recurse/fastexp.html and interpolating on any remainder) then using f(n) = n^n implies f(n)^(1/n) = n to converge on the exact value.

I've been curious about the ridiculous growth of the Stieltjes constants, I think it may be because n! should be n^n instead (related to Stirling's approximation).

There's some implications here, but I think it could have a relationship to higher order functions like the Ackermann function (and its inverse).

I think making a Sacks spiral with the inverse of n^n would be incredibly useful.

Primes follow a pattern up to ~5^2 and ~7! (could be reading into this too much)

I'm sort of intrigued by https://en.m.wikipedia.org/wiki/Stieltjes_constants

In particular the Matsuoka bound uses 10^-4, which could be related to 1/7! (1/5040). (Definitely a hot take.)

Other stuff to try with the Sacks spiral: 1/2.48, 1/2.27

Maybe a Sacks spiral with n^(1/e) and n^0.75679 and n^(1-0.75679) would work.

Or the Euler-Mascheroni constant might make more sense. I was studying that a lot back in the day albeit I remember using 2*.577... (and mistaking it for another constant).

Additionally, the Euler-Mascheroni constant has some similarity to the Riemann Hypothesis and it's close to .5 (the square root).

Other things to test: 1/3, 1/6, 1/sqrt(6)

I should also consider whether a primorial tree would be better (because this is a worse version of a super well-known optimization that I found).

It could still be useful, but mathematicians would definitely call my finding trivial or definitional or something.

I think the patterns work better in the factorial tree but I could be overlooking something.

I suppose you might have to do the square root method, but I'm pretty sure I saw the same pattern as the Euler lucky number diagonals so it won't be necessary as long as you use the (shifted) row index not the number stored.

Addendum: for factorials you use a vector array with gallop search.

Also, while it may appear you need to cache a bunch of squares / hexagonal numbers / octagonal numbers / etc you only need to do ~k operations for k! elements (~k times)

So the work required is maybe ~k^2/k!

Additionally the perfect hashes that store the square numbers and onward can be put in an array (which is obvious-ish but worth mentioning).

In particular, caching squares, hexagonal numbers, octagonal numbers, etc seems paramount to performance.

When I did this in 2013 I was using square roots which have both precision and performance issues.

Hmmm, if I'm right on this there's an incredible amount of caching optimizations available:

Static cache (perfect hash) of first e.g. 2^(32-1) primes
Dynamic cache (vector array with gallop search) -- recently used primes updated at end of algorithm
Memoization (splay tree sorting values over course of algorithm)

You can do the same techniques for:
Factorials (perfect hash)
Squares (perfect hash)
Hexagonal numbers (perfect hash)
...

I've been curious for a while how quickly you could sort using prime number theory.

I think it would work well enough on low orders of magnitude, but I'm curious if it could beat the O(nlgn) sorting bound asymptotically (if that's even possible).