Besides Scott Kim’s “Celebration of Mind” talk discussed in my previous post, I also today attended Gordon Hamilton’s talk on “Mini Mathematical Universes.” (Hamilton is also known as the designer of the board game Santorini (2016).) This was essentially an excuse to talk about a numerical process that Hamilton calls “Integral Fission.”

Define \(\mathrm{fission(N)}\) for an integer \(N\ge 2\) as follows:

• If \(N\) is prime, then the answer is \(N\) itself.
• Otherwise, choose \(L\le R\) such that \(L\cdot R=N\) and the difference \(R-L\) is minimized; the answer is \((\mathrm{fission}(L),\mathrm{fission}(R))\).

For example, \(\mathrm{fission}(42) = ((2,3),7)\); \(\mathrm{fission}(43) = 43\); \(\mathrm{fission}(44) = ((2,2),11)\); \(\mathrm{fission}(45) = (5,(3,3))\); \(\mathrm{fission}(46) = (2,23)\); and \(\mathrm{fission}(48) = ((2,3),(2,(2,2)))\).

Notice that \(\mathrm{fission}(42)\) and \(\mathrm{fission}(44)\) have the same “shape”: if we ignore the numbers and just look at the parentheses, they’re both of the form \(((x,x),x)\).

Hamilton considers the increasing sequence of integers whose fissions yield novel shapes — that is, the sequence consists of only those positive integers whose fission yields a shape not yielded by any smaller integer.

• \(\mathrm{fission}(2)\) is \(x\)
• \(\mathrm{fission}(4)\) is \((x,x)\)
• \(\mathrm{fission}(8)\) is \((x,(x,x))\)
• \(\mathrm{fission}(16)\) is \(((x,x),(x,x))\)
• \(\mathrm{fission}(20)\) is \(((x,x),x)\)
• \(\mathrm{fission}(32)\) is \(((x,x),(x,(x,x)))\)
• \(\mathrm{fission}(40)\) is \((x,(x,(x,x)))\)

This sequence (2, 4, 8, 16, 20, 32, 40…) is OEIS sequence A125508:

2 4 8 16 20 32 40 64 72 88 128 160 176 200 220 256
272 288 320 336 360 400 420 460 480 512 540 544 640
704 864 880 920 1024 1056 1152 1184 1200 1280 1344
1440 1600 1640 1680 1800 1840 1920 2048 ...

Does every prime eventually appear in a leaf?

The sequence of trees involved in OEIS A125508 goes like this:

Two terms further on, we spot our first factor of 3. Eleven terms later, we spot our first 7. So naturally, someone in the webinar asked: “Does every prime number appear as a factor somewhere in this sequence?”

I have no idea how you’d prove such a conjecture. So I wrote a little C++ program (source) to play around with “Integral Fission.”

• Term 7958, which is the integer 126247680, is the first term divisible by 281; by that point we’ve seen every other prime up to 347 inclusive.

• Term 22920, which is the integer 1368482048, is the first term divisible by 349; by that point we’ve seen every other prime up to 653 inclusive.

• Term 61350, which is the integer 8853585920, is the first term divisible by 659; by that point we’ve seen every other prime up to 857 inclusive.

• Term 63826, which is the integer 9758377440, is the first term divisible by 859; by that point we’ve seen every other prime up to 1277 inclusive.

• Term 96572, which is the integer 21258514800, is the first term divisible by 1279; by that point we’ve seen every other prime up to 1481 inclusive.

• Term 128234, which is the integer 36008853504, is the first term divisible by 1483; by that point we’ve seen every other prime up to 1787 inclusive.

• Term 130922, which is the integer 37328558400, is the first term divisible by 1789; by that point we’ve seen every other prime up to 1987 inclusive.

Does the sequence contain any odd number?

I initially conjectured that each term in OEIS A125508 would be divisible by two.

Pseudo-proof: In order to have an odd term, all of the leaves in its decomposition would have to be odd; which means they’d all have to be greater than 2; which means that if you took that same tree and replaced the leftmost leaf with a 2, you’d end up with a smaller integer producing that same shape; contradiction, Q.E.D.

But that’s not a real proof! — because blindly substituting 2 into a leaf won’t always produce a valid fission at all. Consider \(\mathrm{fission}(357) = (17,(3,7))\).

• If you replace the 17 with a 2, you get \((2,(3,7))\ne ((2,3),7)\).
• If you replace the 3 with a 2, you get \((17,(2,7))\ne ((2,7),17)\);
• If you replace the 7 with a 2, you get \((17,(2,3))\ne ((2,3),17)\).

And in fact, the 36857th term of OEIS A125508 is the odd number \(3\,447\,969\,525\). Conjecture busted! Here are the odd terms I’ve seen so far:

36857 3447969525 (((13,(3,5)),(11,(3,(3,3)))),(((3,3),(3,(3,3))),(7,(5,7))))
46174 5277504375 ((((3,3),(3,(3,3))),(11,(3,(3,3)))),(((3,5),(3,5)),(13,(5,5))))
55320 7161167475 ((((3,3),(3,(3,3))),((3,5),(3,7))),((11,(3,(3,3))),((3,5),(3,7))))
57897 7797715695 ((((3,3),(3,(3,3))),(7,(7,7))),((11,(3,(3,3))),((3,5),(3,7))))
58580 7979586615 ((((3,3),(3,(3,3))),(13,(3,(3,3)))),((11,(3,(3,3))),((3,5),(3,7))))
73900 12890101455 ((((3,3),(3,(3,3))),((3,7),(3,7))),((11,(3,(3,3))),((3,5),(3,(3,3)))))
75596 13299311025 ((((3,5),(3,7)),(13,(3,(3,3)))),((11,(3,(3,3))),((3,5),(3,(3,3)))))
78491 14059271655 ((((3,3),37),(13,(3,(3,3)))),((11,(3,(3,3))),((3,5),(3,(3,3)))))
80487 14819232285 (((11,(3,(3,3))),((3,5),(3,(3,3)))),((13,(3,(3,3))),(13,(3,(3,3)))))
80841 14994607815 (((11,(3,(3,3))),((3,5),(3,(3,3)))),(((3,3),(3,(3,3))),(19,(3,(3,3)))))
89972 18326742885 ((((3,3),(3,(3,3))),(19,(3,(3,3)))),((11,(3,11)),((3,5),(3,(3,3)))))
95851 20962690245 (((7,(7,7)),((3,5),(3,(3,3)))),(((3,3),(3,(3,3))),(23,(3,(3,3)))))
104452 24608375505 (((7,(7,7)),((3,5),(3,(3,3)))),(((3,3),(3,(3,3))),((3,(3,3)),(3,(3,3)))))
129536 36673857675 ((((3,5),(3,(3,3))),(13,(5,7))),((13,(3,(3,3))),((3,7),(3,(3,3)))))
138055 41662080999 ((((3,7),(3,7)),(17,(3,(3,3)))),((11,(3,11)),((3,7),(3,(3,3)))))
141799 43826344947 ((((3,7),(3,7)),(17,(3,(3,3)))),((11,(3,(3,3))),((3,(3,3)),(3,(3,3)))))
175066 66169187469 ((((3,7),(3,7)),((3,7),(3,(3,3)))),((11,(3,11)),((3,(3,3)),(3,(3,3)))))

How fast does the sequence grow?

Anecdotally, it seems to grow in fits and starts. For example, of the 100,000,000 integers preceding \(2^{32}\), only 473 of them are terms in the sequence; but of the 100,000,000 integers following \(2^{32}\), 840 of them are in the sequence.

If the count of \(n\)’s prime factors grows as \(\log \log n\), does that mean that we should expect to see \(k\)-leaf trees appearing around \(e^{e^k}\)? But then the number of \(k\)-leaf trees itself grows as \(4^n\)… so should we expect the terms of the sequence to grow roughly exponentially?

Are there any tree shapes that never appear?

I conjecture that every shape of tree must eventually appear somewhere in the sequence — right? Some shapes take a long time to show up, but I think that given any shape of tree, it’s merely a bit of arithmetic to produce some integer that fissions into that particular shape.

After 503 terms, we’ve seen all 14 trees with five prime leaves; the last to show up is \(\mathrm{fission}(212\,060)=((((2,2),5),23),461)\).

After 143871 terms, we’ve seen all 42 trees with six prime leaves; the last to show up is \(\mathrm{fission}(44\,973\,896\,860)=(((((2,2),5),23),461),212081)\).

What if we change the definition of isomorphism?

Watching Hamilton’s YouTube video on “Integral Fission,” I was struck by the fiddliness of having to put the smaller factor on the left every time. What if we eliminate the distinction between the left and right subtrees of a decomposition, so that the tree \(((2,2),5)\) is considered to have the same “shape” as \((2,(2,2))\)?

In that case, we boringly get a subsequence of OEIS A125508:

2 4 8 16 32 40 64 128 160 176 256
512 544 640 704 880 920 1024 1200
1280 1440 1600 2048 2176 2368 2560
2816 3456 4096 8192 8576 8704 ...

What if we change the source being filtered?

Hamilton’s sequence is basically taking the sequence \(2, 3, 4, 5, 6, 7, 8\ldots\) and passing it through this “novelty filter.” What if we took a different sequence to filter, instead? For example, what if we took only the integers divisible by three?

3 6 12 24 42 48 72 84 96 156 192 240
288 300 312 336 360 384 420 480 540
672 696 768 864 966 1056 1152 1176 ...

Or what if we took only the integers divisible by ten?

10 20 30 40 60 80 120 160 200 220 320
360 400 420 460 480 540 600 640 720
800 810 880 920 930 960 1080 1120 ...

Or only the Fibonacci numbers?

2 8 21 144 610 2584 6765 46368 832040
2178309 14930352 102334155 ...

No conclusions here; I’m just playing around with numbers in a very non-mathematician kind of way.

The first 200,000-ish terms of OEIS A125508 are here.