The Good Prime

Yes, there is such a thing as a good prime and it is defined as follows:

A prime \(p_n\) is said to be \( \textbf{good} \) if \(p_n^{^\textbf{2}}>p_{n-i } \cdot p_{n+i} \) for all \( 1 \leq i < n \).

The term was drawn to my attention because the prime associated with my diurnal age today (27737) and its earlier cousin prime (27733) are both good primes. The initial good primes are: 

5, 11, 17, 29, 37, 41, 53, 59, 67, 71, 97, 101, 127, 149, 179, 191, 223, 227, 251, 257, 269, 307, 311, 331, 347, 419, 431, 541, 557, 563, 569, 587, 593, 599, 641, 727, 733, 739, 809, 821, 853

Let's look at 17 as an example where \(17^2=289\). The primes less than it are 2, 3, 5, 7, 11 and 13. The corresponding primes larger than it are 43, 37, 31, 29, 23 and 19. So we have:$$ \begin{align} 2 \times 43 &= 86 < 289 \\ 3 \times 37 &= 111 < 289 \\ 5 \times 31 &=155 < 289 \\ 7 \times 29 &=203 < 289 \\ 11 \times 23 &= 253 < 289 \\ 13 \times 19 &= 247 < 289 \end{align}$$The earliest runs of 2, 3, 4, 5, 6 and 7 consecutive good primes start at 37, 557, 1847, 216703, 6929381, 134193727 and 15118087477. The good primes from 27733 to 40000 are as follows (permalink):

27733, 27737, 28277, 28387, 28403, 28493, 28537, 28571, 28591, 28597, 29833, 29983, 30011, 30059, 30089, 30491, 30631, 30637, 30671, 30757, 30803, 31121, 31139, 31147, 31957, 32027, 32051, 32057, 32297, 32969, 33287, 33311, 33329, 34123, 35729, 35747, 35797, 35801, 35831, 35951, 35963, 36433, 36451, 36467, 36523, 36527, 36671, 38113, 38149, 38167, 38177, 38543, 38557, 38593, 38651, 38669, 39079, 39089

Clearly the primes above and below the aspiring good prime need to be fairly bunched up, especially the ones above, and this is indeed the case for 27733 and 27737.

Mathematics Puzzle Template

There is a type of Mathematical Puzzle that follows the template shown in Figure 1.

Figure 1

The puzzle above isn't too difficult to solve once one realises that the numbers in three out of the four inner quadrants are formed from the two numbers in the corresponding outer part of the quadrant by the formula:$$ \text{inner number = (larger number - smaller number)}^3$$ Thus the missing number is calculated as follows:$$ \begin{align} (8 - 2)^3 &= 6^3\\ &=216 \end{align} $$Removing the numbers from Figure 1 we are left with the (rather crude) template shown in Figure 2.

Figure 2

Using this template, it's easy to come up with other puzzles such as the one shown in Figure 3.

Figure 3

Here the solution lies in the fact that:$$ \text{inner number = (larger number + smaller number) mod 7}$$The solution is thus:$$ \begin{align} (11 + 3) \text{ mod 7 } &= 14 \text{ mod 7}\\ &= 0 \end{align} $$I may create more puzzles in the future using this template.

Density of Primes

It's well known that the density of primes decreases as we proceed along the number line but, in the range of numbers up to 100,000, where can we find intervals where the density of primes is quite high. To quantify this density, let's take a prime and consider the next FIVE primes that follow it. Now let's calculate the difference between this sixth prime and the first and call this difference the "gap". Thus we have primes 1 to 6 and the gap is given by:$$\textbf{gap = prime 6 - prime 1}$$Where is this gap equal to 14 (which is minimum possible)? We'll identify the position by reference to the first prime and the gap will tell us the sixth prime because:$$\textbf{prime 6 = prime 1 + gap} $$And so we have the following gap statistics:$$ \textbf{gaps of 14 occur at }\\ 3, 5$$ $$\textbf{gaps of 16 occur at }\\7, 97, 16057, 19417, 43777$$ $$ \textbf{gaps of 18 occur at} \\11, 13, 29, 223, 1289,\\ 1481, 1861, 4783,5639, 5641, 13679,\\ 27733, 44263, 80669, 88799, 88801, 93479$$ $$\textbf{gaps of 20 occur at}\\17, 23, 41, 53, 59, 89, \\179, 263, 599, 641, 809, 1277, \\1283, 1601, 1607, 3449, 3527, 3911, \\4001, 4637, 5849, 9419, 14543, 18041, \\19421, 21011, 22271, 26681, 26711, 43781, \\45119,51419, 54401, 55331, 62969, 65699, \\71327, 75983, 87539, 88793, 97367, 97841 $$Figure 1 shows a plot of the various primes (up to 100,000) and their associated gaps. The largest gap of 154 occurs at 69499 and thus the interval is from 69499 to 69653.

Figure 1: permalink

What I've considered is just one measure of prime density. The decision to consider the gap between six successive primes is quite arbitrary. I could have considered five or seven.

Runs of Semiprimes

A little investigation has revealed that there are record runs of eight semiprimes that are each separated by one number or, to put it another way, the semiprimes form an arithmetic progression with a common difference of 2. In the range up to half a million, there are four groups of eight such semiprimes. All the numbers are odd because every fourth number is a multiple of 4 and so no such runs of eight even numbers are possible. The reason that the limit is eight semiprimes is that every ninth number is a multiple of 9. The groups are (permalink):

• 8129 ... 8143 (see Table 1)
• 237449 ... 237463 (see Table 2
• 401429 ... 401443 (see Table 3)
• 452639 ... 452653 (see Table 4)

The details are (permalink):

Table 1: permalink

Table 2: permalink

Table 3: permalink

Table 4: permalink

As I later discovered, these four numbers form the initial terms of OEIS A217222.

A217222    Initial terms of sets of 8 consecutive semiprimes with gap 2.

The initial terms are:

8129, 237449, 401429, 452639, 604487, 858179, 1471727, 1999937, 2376893, 2714987, 3111977, 3302039, 3869237, 4622087, 7813559, 9795449, 10587899, 10630739, 11389349, 14186387, 14924153, 15142547, 15757337, 18017687, 18271829, 19732979, 22715057, 25402907

Here are the OEIS comments:

• All terms == 11 (mod 18).
• Also all terms of sets of 8 consecutive semiprimes are odd, e.g., {8129, 8131, 8133, 8135, 8137, 8139, 8141, 8143} is the smallest set of 8 consecutive semiprimes.
• Note that in all cases "9th term" (in this case 8143+2=8145) is divisible by 9 and hence is not semiprime.
• Also note that all seven "intermediate" even integers (in this case {8130, 8132, 8134, 8136, 8138, 8140, 8142}) have at least three prime factors counting with multiplicity. Up to n = 40*10^9 there are 5570 terms of this sequence.

There is another sequence, of which OEIS A217222 is a subsequence, wherein an even semiprime is contained in the run of eight odd semiprimes. This is OEIS A082919.

A082919    Numbers k such that k, k+2, k+4, k+6, k+8, k+10, k+12 and k+14 are semiprimes.

The initial members of this sequence are (members of A217222 are shown in blue):

8129, 9983, 99443, 132077, 190937, 237449, 401429, 441677, 452639, 604487, 802199, 858179, 991289, 1471727, 1474607, 1963829, 1999937, 2376893, 2714987, 3111977, 3302039, 3869237, 4622087, 4738907, 6156137, 7813559, 8090759

Take 9983 as an example. There is still the run of eight odd semiprimes but, between 9985 and 9987, there is 9986 which is also a semiprime. In all the non-blue numbers above, there is only the one even semiprime in the range of 14 numbers, making for a total of nine semiprimes. See Table 5:

Table 5

Here are some of the OEIS comments for this sequence:

• All terms == 11 (mod 18). - Zak Seidov, Sep 27 2012
• There is at least one even semiprime between k and k+14 for 1812 of the first 10000 terms. - Donovan Johnson, Oct 01 2012
• All terms == {29,47,83} (mod 90). - Zak Seidov, Sep 13 2014
• Among the first 10000 terms, from all 80000 numbers a(n)+m, m=0,2,4,6,8,10,12,14, the only square is a(4637) + 2 = 23538003241 = 153421^2 (153421 is prime, of course). - Zak Seidov, Dec 22 2014

Negabinary Niven Numbers

Wow, yesterday's post featured Gray Code Niven Numbers and in today's post we're featuring Negabinary Niven Numbers. Here's what Gemini had to say about negabinary:

Negabinary is a base-negative-2 number system that uses the digits 0 and 1 to represent numbers. It's similar to the binary system, but without the need for a negative sign. 

How to convert to negabinary 

• To convert a decimal number to negabinary, divide the number by -2 repeatedly. 

• Record the non-negative remainder of 0 or 1 each time you divide. 

• Take the remainders in reverse order to get the negabinary expansion.

Why use negabinary?

• Negabinary doesn't require a negative sign, or two's complement.  

• All integers, negative or positive, can be written as an unsigned stream of 1s and 0s.  

• This representation is "more unique" than with a positive base because, without signs, there is not the problem of +0 being equal to -0. 

Related negative-base numeral systems: negadecimal (base −10) and negaternary (base −3). 

There is a great site that converts decimal to negabinary and binary to negabinary and vice versa. See Figure 1. We'll be using it shortly.

Figure 1: link

So what led me to negabinary numbers? Well, the number associated with my diurnal age today (27728) has a property that allows it membership of OEIS A331824.

A331824   Starts of runs of FOUR consecutive positive negabinary-Niven numbers, these are numbers that are divisible by the sum of their digits in their negabinary representation (A027615).

We use the site above to convert the decimal numbers 22728, 22729, 22730 and 22731 to negabinary and then test to see that the total number of 1's for each number divides the number. This is indeed the case. See Table 1.

Table 1: permalink

The initial members of the sequence are 1, 1264, 2104, 2944, 4624, 11888, 23768, 27312, 27728, 31688, 35648. 

Table 2 shows the negabinary representations of the numbers from 0 to 16:

Table 2

Gray Code Niven Numbers

Let's recall a few facts. A Harshad or Niven number is a number that is divisible by its sum of digits. For example, 21 has a sum of digits of 3 and 3 divides 21 to give 7. Thus 21 is a Niven number, at least in base 10. What about in other bases? Well, in base 7, 21 can be represented as 30 with a sum of digits of 3 again. So 21 is a Niven number in base 7 as well. What about in base 2 where it has a representation of 10101. Again the sum of digits is 3 and thus 21 is also a Niven number in base 2. Of course, 21 is not a Niven number in all bases. In base 8, the number is represented as 25 with a sum of 7 which does not divide into it.

Source

Now I've written about Gray Code in an eponymous post on 18th June 2023 so I won't go into the topic again here. Suffice to say that to generate the Gray Code of a number we convert it to binary and make certain changes to the binary digits. Let's illustrate this by way of the number associated with my diurnal age today, 27727. It's binary representation is 110110001001111 and the Gray Code equivalent is 101101001101000. Now how many 1's are there in the latter. There are seven which corresponds of course to its digit sum. Now 7 divides 27727 because its factorisation is 7 x 17 x 233. So 27727 with its digit sum of 25 is not a Niven number in base 10. Nor is it a Niven number in base 2 where there are nine 1's. However, it is a Gray Code Niven number!

These sorts of numbers caught my attention because of OEIS A344344:

A344344  Starts of runs of 4 consecutive Gray-code Niven numbers (A344341: Gray-code Niven numbers: numbers divisible by the number of 1's in their binary reflected Gray code (A005811)).

Figure 1 shows the results for the four consecutive numbers (permalink):

Figure 1

The initial members of OEIS A344344 are:

1, 6, 30, 126, 510, 543, 783, 903, 2046, 2093, 3773, 3903, 7133, 7743, 8190, 8223, 8703, 10087, 12303, 12543, 14343, 14463, 15423, 15903, 16143, 16263, 20167, 22687, 27727, 30247, 30653, 30783, 32766, 35629, ...

Efficient Sorting Algorithm

 Here is a problem that I came across today. Here is the link.

Place each of the numbers from 1 to 15 into the spaces provided so that the sum of any two consecutive spaces is a square number. The following clue was provided: the number 8 must be placed on one end and the number 9 must be placed on the other end.

Without the clue, there are a staggering 1,307,674,368,000 possible permutations (that's over one trillion) but with the clue this reduces to 6,227,020,800 or a little over six billion. However, the clue is very helpful because we know that next to 8 we can only place a 1 and next to the 9 we can only place a 7. So we have:$$9, 7, x, x, x, x, x, x, x, x, x, x, x, 1, 8$$Now next to the 7 we can only place a 2 and next to the 1 we can only place a 15, so we now have:$$9, 7, 2, x, x, x, x, x, x, x, x, x, 15, 1, 8$$Next to the 2 we can only place 14 and next to the 15 we can only place a 10. This gives$$9, 7, 2, 14, x, x, x, x, x, x, x, 10, 15, 1, 8$$Continuing this process, we find 14 can only be paired with 11 and 10 with 6. We now have:$$9, 7, 2, 14, 11, x, x, x, x, x, 6, 10, 15, 1, 8$$We then quickly reach our solution:

The key to solving the problem is to begin and end the sequence of numbers with 8 and 9 or vice versa because these two initial choices determine all the remaining numbers. I asked Gemini to write a Python program to solve the problem but without giving it any clues. I also asked it to explain its thinking. Figure 1 is what it came up with, in about 67 lines of code.

Figure 1: Gemini Link

Here is how Gemini described its thinking:

\( \textbf{Reasoning and Strategies:}\)

is_square(n) \( \textbf{Function} \):

• This function efficiently checks if a number is a perfect square. It calculates the integer square root and compares its square to the original number. 

find_next(current_sequence, remaining_numbers) \( \textbf{Function (Recursive Backtracking:)} \)

• This function uses recursion to explore possible sequences.
• It checks if the current sequence is complete (no remaining numbers).
• For each remaining number, it checks if it forms a square sum with the last number in the current sequence.
• If a square sum is found, it adds the number to the sequence and recursively calls itself with the updated sequence and remaining numbers.
• If no valid next number is found, it backtracks. 

\( \textbf{Optimization} \) 

\( \textbf{Precompute Possible Pairs (Graph Representation): }  \)

• Instead of repeatedly checking for square sums, we precompute all possible pairs of numbers that add to a square.
• This is stored in the possible_pairs dictionary, which represents a graph where numbers are nodes, and edges exist between numbers that form a square sum.
• This optimization significantly reduces the number of square sum calculations. 

\( \textbf{Optimization} \) 

\( \textbf{Start with Numbers with Fewer Possible Pairs:} \)

• The sorted_numbers list is created by sorting the numbers based on the number of possible pairs they have.
• Starting the search with numbers that have fewer possible pairs reduces the branching factor in the recursive search. This means the algorithm explores fewer potential paths, leading to faster results.
• This is a heuristic that helps avoid exploring large portions of the search space that are unlikely to lead to a solution. 

\( \textbf{Backtracking Efficiency}: \)

• The recursive backtracking algorithm is designed to efficiently explore the search space. When a dead end is encountered (no valid next number), the algorithm immediately backtracks to the previous decision point, avoiding unnecessary exploration of other paths.
• By combining the precomputation of possible pairs and the heuristic of starting with numbers with fewer options, the backtracking algorithm becomes much more efficient than a naive brute-force approach.

The algorithm (permalink) is easily adapted for longer runs of numbers. For example, let's say we want to arrange the number from 1 to 35. Here is one configuration (generated almost instantly):

[18, 7, 2, 14, 11, 5, 31, 33, 3, 22, 27, 9, 16, 20, 29, 35, 1, 8, 28, 21, 4, 32, 17, 19, 6, 30, 34, 15, 10, 26, 23, 13, 12, 24, 25] ... permalink