Postscript to my talk "New Gilbreath Conjectures, Sum and Erase, Dissecting Polygons, and Other New Sequences", given in Doron Zeilberger's Rutgers Experimental Mathematics Seminar, on September 14 2023
N. J. A. Sloane,
Last revised October 2 2023
Summary: A list of comments on some of the topics discussed in the talk, and some corrections.
This document will be posted on the seminar webpage https://sites.math.rutgers.edu/~zeilberg/expmath/archive23.html, and also on my homepage, http://neilsloane.com. I will keep the version on my homepage up-to-date with further comments as they come in.
The talk
--------
A video of the talk can be found on Vimeo, here:
https://vimeo.com/866583736?share=copy
The slides are on my home page, see http://neilsloane.com
There are also links to the video and the slides from the Experimental Mathematics Seminar homepage https://sites.math.rutgers.edu/~zeilberg/expmath/, see the Archive section of that page, https://sites.math.rutgers.edu/~zeilberg/expmath/archive23.html and scroll all the way to the bottom.
Notes on the talk
-----------------
The topics are discussed in the same order as in the talk.
Counting
--------
The first colored slide: this shows a 3 X 3 grid of squares, or equivalently a 4 X 4 grid of points. Apologies for using both notations. (A chessboard can be regarded as an 8 X 8 grid of squares, or a 9 X 9 grid of points.)
Scott Shannon's First Circle Counting Problem
----------------------------------------------
Scott Shannon remarks that his conjecture in A358746 might not be too difficult to prove.
Scott Shannon's Second Circle Counting Problem
----------------------------------------------
This seems like a very basic question in combinatorial geometry. In slide 12 of the talk, I mentioned three sequences of Scott Shannon's, which give the numbers of vertices, circles, and regions at the n-th stage. The first and third sequences were in the OEIS, as A359569 and A359570. Scott has computed two more terms for the second sequence, which is now A365669. Here are the known terms (* indicates a new term):
n---A359569-----A365669-----A359570
0---------2-----------0-----------0
1---------4-----------2-----------3
2--------14-----------6----------21
3------6562---------114*-------7169
4---------?----42103152*----------?
Scott remarks that 6^2/2 is close to 14 (just a bit less), and 114^2/2 is close to 6562 (just a bit less), so if that holds we get an estimate of about 880x10^12 for the vertex count A359569(4). So to find further terms it may be necessary to analyze the problem rather than using brute force!
Dissecting a regular polygon into a rectangle (with Gavin Theobald)
-------------------------------------------------------------------
A first draft of our paper, "On Dissecting Polygons into Rectangles", is now on my homepage
(see http://neilsloane.com/doc/Rectangle4.pdf)
and will soon be posted to the arXiv.
A real error
------------
At about 22 minutes into the talk, in discussing the 9-gon to rectangle dissection, the text says theta = Pi/11, but this should be theta = Pi/9. To make things worse, I SAID "Pi over 11", twice.
Monotiles
---------
At about 25 minutes in, discussing monotiles, there are simpler monotiles that can be obtained from a pentagon in two pieces, see OEIS entry A362938. This OEIS entry has a large number of monotiles obtained by Gavin Theobald from regular n-gons with n < 20. Many of them are quite astonishing.
The New Gilbreath Conjectures
---------------------------
There were many comments, so I have collected them at the end of this document.
Eric Angelini's Sum and Erase sequence
--------------------------------------
At 34 minutes: Sum and Erase slide (1); 31813 should be 31913.
I didn't realize that it was Eric's birthday two days before the talk. Happy Birthday (a bit late)!
One of the earliest and greatest of Eric's many inventions was the "Commas sequence", A121805, and to celebrate his birthday his son has made a brilliant and hilarious video based on that sequence:
Lorenzo Angelini, Happy birthday Éric!!, Youtube video.
Report on Status of OEIS
------------------------
In the "statistics" section I should have mentioned that the OEIS has now been cited over 11,000 times in the literature. See https://oeis.org/wiki/Works_Citing_OEIS for the list of citations.
-------------------------------------------------------------------------------------------------------
The New Gilbreath Conjectures
-----------------------------
In the talk, I repeated the old canard that Proth gave a false proof. This is simply not true. See for example the de Reyna link.
1. Collected references about the Gilbreath Conjecture
- Chris Caldwell, Gilbreath's Conjecture, Prime Glossary, https://t5k.org/glossary/page.php?sort=GilbreathsConjecture
- Zachary Chase, A Random Analogue of Gilbreath’s Conjecture, arXiv:2005.00530, May 1, 2020.
- C. Cobeli and A. Zaharescu, A game with divisors and absolute differences of exponents, Journal of Difference Equations and Applications, Vol. 20, #11 (2014) pp. 1489-1501, DOI: 10.1080/10236198.2014.940337. Also available as arXiv:1411.1334 [math.NT], 2014.
- David Eppstein, "Anti-Gilbreath sequences". https://11011110.github.io/blog/2011/02/20/anti-gilbreath-sequences.html, Feb 20, 2011
- M. Gardner, The Last Recreations, Springer, 1997. Pages 195-196 discuss Gilbreath's conjecture and mention Hallard Croft's suggestion as to which sequences share the Gilbreath property that the Gilbreath transform is all-1's.
- N. Gilbreath, Processing process: The Gilbreath conjecture, J. Number Theory, 131 (2011), 2436-2441.
- R. K. Guy, Unsolved Problems in Number Theory, Springer-Verlag, 1994, New York, NY, Section A10.
- A. M. Odlyzko, "Iterated absolute values of differences of consecutive primes". Mathematics of Computation. 61 (203) 1993, 373–380.
- F. Proth, "Théorèmes sur les nombres premiers," C. R. Acad. Sci. Paris, 85 (1877) 329-331.
- F. Proth, “Sur la Serie des nombres premiers”, Nouvelle Correspondance Math´ematique, 4 (1878) 236-240.
- Arias de Reyna, "Gilbreath’s conjecture", https://institucional.us.es/blogimus/en/2020/07/gilbreaths-conjecture/, July 9, 2020 [An excellent survey, which I would have mentioned in the talk if I had known about it.)
OEIS entries related to the conjecture:
- Gilbreath conjecture for primes: A036262*, A036261
- Gilbreath transforms of: Fibonacci numbers: A011655; Lucky numbers: A054978; partition numbers: A196251; primes p(n): A036261, A036262; A358691, A117069; semiprimes: A365939, A131749 sigma: A362451, A362456, A362457; sigma(n)-n: A362452; tau: A361897, A362450;
- Other Gilbreath-related sequences: there are many other related sequences in OEIS, searcg under "Gilbreath"
2. General comments about the Gilbreath Transform (GT) from Hugo van der Sanden, originally sent May 10, 2023, slightly revised Sept. 14 2023:
(start)
There seem to be two main features: the parity of the values, and the magnitude.
The parity of GT(primes), GT(lucky) and GT(EulerPhi) is in each case quite clear: this is what GT() gives when the input sequence has parity (0, 1*), (1*), or (1, 1, 0*) respectively.
As for the magnitude: taking absolute differences has a damping effect over a sequence, so applying that repeatedly means it becomes quite hard for GT to emit larger values.
Here are two ways to look at the damping effect:
First, consider GT(A001792 = (n+2)*2^(n-1)) = (A000027 = n). I think it should be fairly easy to prove that this is the only sequence of positive integers that gives A000027. This tells us something about the rate of growth of the type of sequence that can give a growing Gilbreath transform.
Second, consider the sequence of lists obtained by applying absolute differences starting from the first 10^k primes, and look at how many elements of the list are still > 2, and the position of the first such element.
With 10 primes, the first absolute differences show 4 of the 9 values being > 2, with the first such at position 3; the second absolute differences clear out all of them, so every subsequent list has only values <= 2.
With 100 primes the count goes:
73, 44, 32, 25, 19, 16, 13, 10, 5, 1, 0, 0, ...
and position of first element > 2 is:
3, 8, 14, 14, 25, 24, 23, 22, 25, 59
.. so it takes 11 iterations of the 99 available to clear out all values greater than 2.
With 1000 primes it takes 35 iterations to clear out all values > 2, and the position of the first value > 2 at the 34th iteration was 866. With 10000 primes it takes 65 iterations (final position 5940), and with 100000 primes it takes 97 iterations (final position 92620).
So probabilistically, at least, it seems there is no realistic chance of a counterexample.
sigma(n) is more interesting in this regard, since it seems to have enough lumpiness in its nature to keep emitting higher values. I'm not sure whether this tells us anything much about sigma(n), except in a very broad sense about lumpiness (which may be an interesting research topic in its own right, but well out of my expertise).
tau(n) is also closer to the "lumpy enough" cusp, from the other side. Since we don't have a simple parity pattern we need to wait for all elements > 1 to disappear; then the number of iterations required before a 10^k list is fully reduced goes like:
(from k=1): 2, 30, 74, 376, 1020, 3903, ...
.. but it would need to increase by a factor much closer to 10 each time to have a chance of actually emitting a GT() value > 1.
(end)
---
3. Comments from Sean A. Irvine, Jacob Schulz, and Robert Dougherty-Bliss:
---------------------------------------------------------------------------
Sean Irvine, Sept 18 2023:
I computed 1 million terms of the Gilbreath transform of phi and the (1,0) pattern continues at least that far.
Sean Irvine, Sept 18 2023:
In terms of getting some traction on the sequences arising from the Gilbreath transform, it looks to me like the Gilbreath transform of the Fibonacci numbers which is apparently 0,1,1 repeated should be easy to prove. In this case, terms with index >= n in row n, are simply the Fibonacci numbers themselves and that after each set of three rows we have one additional copy of 0,1,1 at the start of the row. So I think you could make this more formal with some kind of induction looking back 3 rows?
1: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
2: 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
3: 1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
4: 0, 1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
5: 1, 0, 1, 1, 0, 1, 1, 2, 3, 5, 8, 13, ...
6: 1, 1, 0, 1, 1, 0, 1, 1, 2, 3, 5, 8, ...
7: 0, 1, 1, 0, 1, 1, 0, 1, 1, 2, 3, 5, ...
...
Jakob Schulz, Sept 19, 2023:
You can also just look back one row for a formal proof: Let d(n, 0) := F(n), and d(n, k+1) := |d(n, k) - d(n+1, k).
Claim: d(n, k) = ...
... F(n-k) if n >= k
... 0 if n <= k and n and k are equivalent mod 3
... 1 if n <= k and n and k are not equivalent mod 3
(Note that the patterns overlap if n=k, but they result in the same value.)
Do induction on k. The case k = 0 is trivial.
In the induction step, consider these cases:
Case 1: n >= k + 1
Case 2: n < k + 1
...Case 2.1: n and k+1 are equivalent mod 3
...Case 2.2: n+1 and k+1 are equivalent mod 3
...Case 2.3: n+2 and k+1 are equivalent mod 3
Inserting the induction hypothesis and doing simple calculations (using that F(n+1-k)-F(n-k) = F(n-(k+1)) in Case 1) completes the proof of the claim.
Robert Dougherty-Bliss, Sept 20, 2023
Even better, this example generalizes to arbitrary initial conditions.
If a(n) = a(n - 1) + a(n) with initial conditions a(0) = x and a(1) = y, then the Gilbreath transform of a(n) is eventually periodic, repeating 0, gcd(x, y), gcd(x, y) forever.
Here are the first 20 terms of the Gilbreath transform of sequences with various initial conditions (x, y):
(0, 1): 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1
(2, 10): 8, 6, 2, 4, 2, 2, 0, 2, 2, 0, 2, 2, 0, 2, 2, 0, 2, 2, 0
(5, 15): 10, 5, 5, 0, 5, 5, 0, 5, 5, 0, 5, 5, 0, 5, 5, 0, 5, 5, 0
(20, 6): 14, 6, 8, 2, 6, 4, 2, 2, 0, 2, 2, 0, 2, 2, 0, 2, 2, 0, 2
And here are the first 40 terms of (101, 7):
94, 7, 87, 80, 7, 73, 66, 7, 59, 52, 7, 45, 38, 7,
31, 24, 7, 17, 10, 7, 3, 4, 1, 3, 2, 1, 1, 0, 1, 1,
0, 1, 1, 0, 1, 1, 0, 1, 1.
This is because the initial conditions (x, y) are eventually taken to either (y mod x, x) or (-y mod x, x), and applying this repeatedly leads to (0, gcd(x, y)), which cycles.
Sean Irvine, Sept 20 2023:
Below are several iterations of abs(delta(phi)). I can easily generate more or wider. But even this small table does show what is happening in an empirical sense and seems to match up with the general comments made by Hugo.
The reason the leftmost column is (0,1)* is that the second column is 1* (like what happens with primes), and that in turn is because the third column appears to be always 0 or 2 and it actually doesn't matter the fine structure of that column. Of course, everything beyond the second column will always be even. It does appear to be the case that most of the table quickly decays to 0 or 2, presumably because phi does not introduce larger values at a quick enough rate - like what Hugo was saying. I would go so far as to conjecture that everything below the main diagonal is at most 2.
1, 1, 2, 2, 4, 2, 6, 4, 6, 4,10, 4,12, 6, 8, 8,16, 6,18, 8,12,10,22, 8,20
0, 1, 0, 2, 2, 4, 2, 2, 2, 6, 6, 8, 6, 2, 0, 8,10,12,10, 4, 2,12,14,12, 8
1, 1, 2, 0, 2, 2, 0, 0, 4, 0, 2, 2, 4, 2, 8, 2, 2, 2, 6, 2,10, 2, 2, 4, 2
0, 1, 2, 2, 0, 2, 0, 4, 4, 2, 0, 2, 2, 6, 6, 0, 0, 4, 4, 8, 8, 0, 2, 2, 2
1, 1, 0, 2, 2, 2, 4, 0, 2, 2, 2, 0, 4, 0, 6, 0, 4, 0, 4, 0, 8, 2, 0, 0, 8
0, 1, 2, 0, 0, 2, 4, 2, 0, 0, 2, 4, 4, 6, 6, 4, 4, 4, 4, 8, 6, 2, 0, 8, 4
1, 1, 2, 0, 2, 2, 2, 2, 0, 2, 2, 0, 2, 0, 2, 0, 0, 0, 4, 2, 4, 2, 8, 4, 4
0, 1, 2, 2, 0, 0, 0, 2, 2, 0, 2, 2, 2, 2, 2, 0, 0, 4, 2, 2, 2, 6, 4, 0, 4
1, 1, 0, 2, 0, 0, 2, 0, 2, 2, 0, 0, 0, 0, 2, 0, 4, 2, 0, 0, 4, 2, 4, 4, 4
0, 1, 2, 2, 0, 2, 2, 2, 0, 2, 0, 0, 0, 2, 2, 4, 2, 2, 0, 4, 2, 2, 0, 0, 0
[20 rows omitted here]
...
[At Sean's suggestion I added the third column, halved, to the OEIS: see A365938]
End of document
Neil Sloane
(njasloane on gmail)
Sept 23 2023