First, a little algebra.
For b >= 3 and z >= 1, define
t = b^(2*b-4)
u = 1 + b + b^2 + .. + b^(b-2) = (b^(b-1)-1)/(b-1)
v = 1 + t + t^2 + .. + t^(z-1) = (t^z-1)/(t-1)
Then the value of the base-b pattern with z zigzags
can be written as:-
If z=1, v=1 and N = u^2.
This solves problem 1), with the answer No.
If b = +1 mod n,
t = +1 mod n,
u = b-1 = 0 mod n,
v = z mod n,
so N = -z+1 mod n.
So n | N if z = +1 mod n.
Taking n = 2, we find that if b is odd, then z must
be even, which solves problem 2).
If b = -1 mod n,
t = +1 mod n,
u = 0 mod n (b odd) or +1 mod (b even),
v = z mod n,
so N = -z+1 mod n (b odd) or +1 mod n (b even).
So n | N if z = +1 mod n (b odd), n does not
divide N (b even).
Taken together with the above result for b = +1 mod
n, this answers problem 3).
Now for questions 4) (a) and (b).
For b <= 10, and up to the stated maximum values of z
(in brackets) which correspond to numbers of about 40,000 digits, I
have found the following primes:-
b z
3 2,4,56,310,1014,1028,1174,1872,2436,4694 (<=10000)
4 2,3,36,89,431,1170,4319 (<=10000)
5 0 (<=10000)
6 50,1310 (<=6000)
7 78 (<=5000)
8 4,9 (<=4000)
9 0 (<=3000)
10 6 (<=2000)
Also, the following specific new primes not given in
the original Puzzle:-
b z
20 120 (<=500)
21 28 (<=500)
51 10 (<=100)
124 26 (<=50)
134 10 (<=50)
What distribution of these primes is to be expected?
Write B = (2*b-4)*ln(b).
Then, for z >> 1, we can approximate
N(b,z) ~ exp(B*z).
For fixed b, there are z numbers N(b,z) <= X=exp(B*z),
i.e. z = ln(X)/B.
Differentiating, the number of Zigzag numbers in the range [X,X+dX] is
(dX/X)/B.
Assuming these are not special, the probability that each is prime is
1/ln(X).
So the expected number of Zigzag primes in the range [X,X+dX] is
(dX/X)/(B*ln(X)).
Integrating, the expected no. of Zigzag primes <= X is approximately
ln(ln(X))/B,
i.e. the expected no. of Zigzag primes for z <= Z is
ln(B*Z)/B.
This would give the following table of expected counts,
for reasonably achievable values of Z:-
b ln(b) B Z=10^1 Z=10^2 Z=10^3 Z=10^4 Z=10^5
3 1.099 2.198 1.406 2.454 3.501 4.549 5.596
5 1.609 9.654 0.473 0.712 0.950 1.189 1.427
10 2.303 36.85 0.160 0.223 0.285 0.348 0.410
20 2.996 107.9 0.065 0.086 0.107 0.129 0.150
50 3.912 375.6 0.022 0.028 0.034 0.040 0.046
100 4.605 902.6 0.010 0.013 0.015 0.018 0.020
150 5.011 1483 0.006 0.008 0.010 0.011 0.013
200 5.298 2098 0.005 0.006 0.007 0.008 0.009
In fact, though, these are underestimates, as they
assume that N(b,z) has the same chance
of being divisible by the various primes as a "typical" number of that
size.
Define a "goodness" factor G(b) to be the factor by
which the probability of being prime exceeds the "typical"
probability.
Studying only primes up to 47, we find that the primes
which can divide N(b,z) are:-
3 2[2],23[11]
4 3[3],7[3],17[17],19[9],23[11]
5 2[2],3[3],7[7],13[2],41[10],47[23]
6 5[5],11[5],19[9],23[11],47[23]
7 2[2],3[3],11[11],19[3],43[3]
8 5[5],7[7],13[13],37[37],43[7]
9 2[2],5[5],17[4],23[11],29[29],31[15],41[2]
10 3[3],17[17],19[9],31[15],37[3],43[21],47[23]
where the [n] figure after each is the period with which it appears as
a divisor.
Taking just the last row, for example, the calculation
of G looks like this:-
1/G(10)=(1/2)*(4/5)*(6/7)*(10/11)*(12/13)*((18/19)/(8/9))*(22/23)*(28/29)*
((30/31)/(14/15))*(36/37)*(40/41)*((42/43)/(20/21))*((46/47)/(22/23))=0.2922
Using these approximate values of G(b) for 3 <= z <= 10, z <= z_max,
here is a table comparing the predicted counts G*ln(B*z_max)/B with
the actual counts listed above:-
b G(b) B z_max predicted actual
3 3.24 2.198 10000 14.74 10
4 3.66 5.544 10000 7.210 7
5 1.82 9.654 10000 2.164 0
6 3.57 14.34 6000 2.829 2
7 2.19 19.46 5000 1.293 1
8 3.81 24.95 4000 1.758 2
9 2.36 30.76 3000 0.877 0
10 3.42 36.85 2000 1.040 1
The agreement is seen to be quite good, and gives
confidence in the correctness of these heuristics.
As another test of the formula, the expected no. of
primes in the range 101<=b<=200 for z <= 50, using the average values
of B(150)=1483 and G=3.0, is:
100*G*ln(B*Z)/B = 2.25.
In fact, there are 2 primes in this range, as listed
above.
So, we are lead to the Conjecture:
For each b >= 3, the number of Zigzag primes with z <= z_max is
approximated by
G*ln(B*z_max)/B,
where B(b) = (2*b-4)*ln(b),
and G(b) is an in-principle-calculable function of b, with values in
the approximate range 1.0 - 5.0.
In particular, therefore, both questions (a) and (b) in
the second Part of this puzzle most probably have the answer Yes.
However, any proof is certainly far out of reach,
remembering that the related
conjecture that there are infinitely many Mersenne primes is still
unsettled
