[seqfan] Re: Gilbreath mysteries

Wed May 10 15:27:16 CEST 2023

It is not entirely clear to me _what_ you find surprising about these
transforms. 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) seems in each case
quite clear: this is what GT() gives when the input sequence has parity
(0, 1*), (1*), or (1, 1, 0*) respectively.

The magnitude is in general not a surprise to me, since the "absolute
difference" has a damping effect over a sequence, and we are applying
it repeatedly.

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 subsequence 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 interations (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.

Hugo

Neil Sloane <njasloane at gmail.com> wrote:
:(Apologies for double posting, but I would really like to know the answers)
:
:1. In 1958 the magician Norman L. Gilbreath observed that if you construct
:an array in which the first row are the primes and subsequent rows are the
:absolute values of the differences of the previous row,
:
:you get an array (A036262)
:
:
:2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101
:...
:
:1 2 2 4  2  4  2  4  6  2  6  4  2  4  6  6  2  6  4  2  6  4  6  8  4   2
:...
:
:1 0 2 2  2  2  2  2  4  4  2  2  2  2  0  4  4  2  2  4  2  2  2  4  2   2
:...
:
:1 2 0 0  0  0  0  2  0  2  0  0  0  2  4  0  2  0  2  2  0  0  2  2  0   0
:...
:
: ...
:
:
:in which the first column appears to be 2 1 1 1 1 .... This is astonishing
:but has never been proved. See R. K. Guy, Unsolved Problems in Number
:Theory, Sec. A10. This was already noticed by Proth in 1878,
:
:F. Proth, <a href="
:http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN598948236_0004&DMDID=DMDLOG_0076&IDDOC=630831">Sur
:la sÃ©rie des nombres premiers</a>, Nouv. Corresp. Math., 4 (1878)
:236-240.who gave what is said to be a false proof.
:
:
:2. If S is a sequence with offset o ("oh"), I define its Gilbreath
:transform GT(S) (with the same offset) in the analogous way (see A362451
:for precise definition). The Gilbreath conjecture is that GT(primes) =
:2,1,1,1,...
:
:
:3. Ten days ago Wayman Eduardo Luy and Robert G. Wilson observed in effect
:that GT(tau) (where tau is the number of divisors function) appears to be a
:sequence of 0's and 1's. This was also a surprise, and also seems to be
:unproved. See A361897, A362450, A462453, A362454.
:
:
:This led me to look at other number-theoretic sequences.
:
:
:4. The sum of divisors function sigma(n) (A000203). The Gilbreath transform
:(A362451) begins
:
:
:1, 2, 1, 1, 1, 2, 1, 0, 0, 1, 0, 4, 0, 3, 0, 2, 1, 1, 1, 0, 1, 1 ...
:
:
:and appears to be mostly 0's and 1's, interrupted by occasional geysers of
:increasing height and duration (see A362456, A362457). Is there any
:explanation for this?  The sum of aliquot parts function A001065 has a
:similar Gilbreath transform to sigma (see A362452).
:
:
:5. It has been suggested that having G.T. equal to 1,1,1,... should hold
:for other sequences with similar properties to the primes. Does anyone know
:of other examples?
:
:
:6. The Lucky numbers A000959 are similar to the primes in some ways. But
:the G.T. of the Lucky numbers is A054978, which begins
:
:
:1, 2, 2, 0, 0, 0, 2, 2, 2, 0, 0, 0, 2, 0, 2, 0, 0, 2, 0, ...
:
:
:If the initial 1 is deleted and the terms are divided by 2, we get what
:appears to be a 0,1 sequence A362460. Why is this?
:
:
:
:7. The G.T. of the Euler phi function A000010 appears to be the period-2
:sequence 1,0,1,0,... (see A362913). Is this obvious? Or is it as mysterious
:as the Gilbreath conjecture?
:
:--
:Seqfan Mailing list - http://list.seqfan.eu/