30 semiprimes, each less than 10
8, form an arithmetic sequence with strictly positive common difference.
Determine all of them.
Note: A semiprime is the product of exactly two primes.
*** For an extra challenge only, find a semi-analytic solution (simple calculator + p&p) to this puzzle.
Prerequisites:
I If d is odd, the maximum length of the list is 3, by a modular argument.
II If d is even, the maximum length of the list is P^2-1, where P is the smallest prime that is not a factor of d, by a similar modular argument.
III For completeness, if n primes P(1) to P(n) are in arithmetic sequence, then their prime multiples are also: https://en.wikipedia.org/wiki/Primes_in_arithmetic_progression
Say, {(0,199), {1, 409}, {2, 619}, {3, 829}, {4, 1039}, {5, 1249}, {6, 1459}, {7, 1669}, {8, 1879}, {9, 2089}} so e.g. twice (or any other prime) times these numbers will comprise an all semiprime list.
IV Let A=the set of primes {2,3,5,...} in the closest factorial less than R. Then A has 2 disjoint subsets:
(1) A(1), the primes that divide d, the common difference.
(2) A(2), the remaining primes in A.
V Assume that prime P is in A(2). Call the list S, and the nth semiprime in the list entry S(n). By a similar modular argument, every Pth entry in the list must be divisible by P - every 3rd by 3, every 5th by 5, and so on.
The Problem:
Let L = the desired length of the list of semiprimes
Let R = the range in which all the semiprimes must fall
For L = 30, R=10^8, 2*3*5*7*11*13*17*19<100000000<2*3*5*7*11*13*17*19*23
Then by II and IV, {2,3,5} are in A(1) and {7,11,13,17,19} are either in A(1) or A(2). Accordingly, d=30k for some k, whose prime factors include every member of A(1), and S(1) to S(30) include semiprimes whose prime factors include every member of A(2), each of which appears at least floor (L/P) times in the list.
Example: Say S(2) is divisible by 7, and S(3) is divisible by 11.
S(1) ...
S(2) 7*(some prime)
S(3) 11*(some prime)
S(4) ...
S(9) 7*(some prime)
S(10) ...
S(14) 11*(some prime)
S(15) ...
S(16) 7*(some prime)
S(17) ...
S(23) 7*(some prime)
S(24) ...
S(25) 11*(some prime)
etc.
Note however that if, say, S(1) was divisible by 11, then S(2) cannot be divisible by 7, since that would imply that S(23) was divisible by both 7 and 11, a contradiction. This may be considered a form of interference pattern. Hence, the larger L is, the less likely it is (subject to III above) that a very small prime will be in A(2) rather than A(1) because of the high probability that its positions in S will interfere with some other small prime. Contrariwise, there is an enhanced probability that small primes just larger than those in A(1) or A(2) will also appear in S, simply because of the need to fill all positions in S.
Putting this together, there is a high probability that d will be at least a multiple of, say, 2310, will contain no prime factors greater than, say, 101, and that the primes between 23 and 101, weighted towards the lower end of that range, will likely figure as components of the semiprimes in S.
As a final refinement, we can classify all lists depending on the value of the components of their entries, mod4. In principle (subject to III above) there are 3 possibilities for each entry: both components worth 1, mod4; both worth 3, mod4; one of each. Call the first two, paired, and the third, unpaired.
If d comprises only multiples of 2^2 and 3, then either every entry is paired, or none is:
Example: d = 4, S(1) = 201, d = 32,S(1) = 133: all entries paired - either both 3, mod 4, or both 1, mod 4.
Example: d = 72, S(1) = 635: all entries unpaired - of the forms {1,3} mod4 or {3,1} mod4.
In all other cases, entries alternate strictly between paired and unpaired:
Example: d = 2, S(1) = 8129: d = 6, S(1) = 186779: d=198, S(1) = 2215: strictly alternating
Example: d = ennugur, S(1) = ergpngdu, L=30: strictly alternating.
Edited on November 20, 2022, 10:55 pm
|
Posted by broll
on 2022-11-20 22:53:33 |