Group Abstract Group Abstract

Message Boards Message Boards

2
|
7.2K Views
|
2 Replies
|
2 Total Likes
View groups...
Share
Share this post:

Find prime number closest to any integer (upper side)

Posted 6 years ago

Here is a program that searches for a prime number closest to an arbitrary integer.? However, there are conditions. The condition is that the specified integer is $5$ or more and the search is limited to the upper side.

Prime numbers greater than $5$ can be determined by the following four equations:

$$\begin{eqnarray} n&=&6 s_1^2+(6 s_1-1)(m_1-1)\tag{1a} \\ n&=&6 s_2^2+6 s_2+1+(6 s_2+1)(m_2-1)\tag{1b} \\ n&=&6 s_3^2-2 s_3+(6 s_3-1)(m_3-1)\tag{1c}\\ n&=&6 s_4^2+2 s_4+(6 s_4+1)(m_4-1)\tag{1d} \end{eqnarray}$$

$$\begin{equation}n=1,2,3\cdots\end{equation}$$

Equations ( $1{\rm a}$) and ( $1{\rm b}$) determine prime numbers of type ( $6n-1$), and equations ( $1{\rm c}$) and ( $1{\rm d}$) determine prime numbers of type ( $6n + 1$). Given an arbitrary positive integer $n$ in equation ( $1$) and there are no integer solutions in $s$ and $m$, $n$ determines the prime number. If there is no integer solution for $s$ and $m$ in equations ( $1{\rm a}$) and ( $1{\rm b}$), let $n$ be $n_m$. Similarly, in equations ( $1{\rm c}$) and ( $1{\rm d}$), $n$ is expressed as $n_p$ when there is no integer solution for $s$ and $m$. The prime number is determined from $n_m$ and $n_p$ according to equation ( $2$).

$$\begin{eqnarray} (6n-1)\text{ type prime}&=&6n_m-1\tag{2a} \\ (6n+1)\text{ type prime}&=&6n_p+1\tag{2b} \\ \end{eqnarray}$$

$$\begin{equation}n_m\ {\rm and}{\text{ }}n_p: {\rm In\ Equation\ (1),{\it n}\ when\ there\ is\ no\ integer\ solution\ for\ {\it s}\ and\ {\it m}.}\end{equation}$$

Here is a program that uses this equation ( $1$) and ( $2$) to find the nearest prime number to an arbitrarily specified positive integer ${\rm j}$. There is a relation $n=(\;{\rm j}-1)\,/\,6\;$ between ${\rm j}$ and $n$. I wrote this in Mathematica as $n = {\rm Quotient}\, [(\,{\rm j}-1), 6]\,$ and converted ${\rm j}$ to $n$. If any integer is input to ${\rm j}$, the prime number closest to ${\rm j}$ is output. Search the range of $n$ to $ (n + 100)$.

j = 5;

Clear[nm, np, pm, pp, minp];
n = Quotient[(j - 1), 6];
If[j >= 5 && n >= 0 && IntegerQ[j],
  Do[{dat1 = 
     FindInstance[
      6*s1^2 + (6*s1 - 1)*(m1 - 1) == n && 0 < s1 && 0 < m1, {s1, m1},
       Integers];
    dat2 = 
     FindInstance[
      6*s2^2 + 6*s2 + 1 + (6*s2 + 1)*(m2 - 1) == n && 0 < s2 && 
       0 < m2, {s2, m2}, Integers]};

   If[dat1 == {} && dat2 == {}, nm = n, nm = 0]; 
   If[dat1 == {} && dat2 == {} && ((6*nm - 1) - j) >= 0, Break[]], {n,
     n, n + 100}];

  Do[{dat3 = 
     FindInstance[
      6*s3^2 - 2*s3 + (6*s3 - 1)*(m3 - 1) == n && 0 < s3 && 
       0 < m3, {s3, m3}, Integers];
    dat4 = 
     FindInstance[
      6*s4^2 + 2*s4 + (6*s4 + 1)*(m4 - 1) == n && 0 < s4 && 
       0 < m4, {s4, m4}, Integers]};

   If[dat3 == {} && dat4 == {}, np = n, np = 0]; 
   If[dat3 == {} && dat4 == {} && ((6*np + 1) - j) >= 0, Break[]], {n,
     n, n + 100}];

  Print["====== The calculation results are shown below. ======"];

  If[nm > 0, pm = 6*nm - 1, pm = 0];
  If[np > 0, pp = 6*np + 1, pp = 0];
  If[pm >= 1 && pp >= 1, minp = Min[pm, pp], minp = Max[pm, pp]];

  Print["j = ", j];
  If[Or[pm >= 1, pp >= 1], 
   Print["Prime number closest to j (upper) = " , minp], 
   Print["Prime number closest to j (upper)= There is no solution in \
the searched interval."]];

  If[Or[nm >= 1, np >= 1], Print["difference = ", minp - j], 
   Print["difference = -"]];

  If[Or[nm >= 1, np >= 1], Print["PrimeQ = ", PrimeQ[minp]], 
   Print["PrimeQ = -"]];

  If[Or[pm >= 1, pp >= 1], Print["Enter j for the next search. "], 
   Print["There is no solution for this interval. If you want to \
continue, start with the next j. j = ", (n + 101)*6]], 
  Print["***** ! Please enter an integer greater than 5 *****"]];

The calculation result is shown as follows. This is an example when ${\rm j} = 5$.

====== The calculation results are shown below. ======
j = 5
Prime number closest to j (upper) = 5
difference = 0
PrimeQ = True
Enter j for the next search.

The closest prime number for ${\rm j} = 5$ is $5$, so the difference is difference $= 0$. “${\rm PrimeQ}$” confirms that it is a prime number.

Let's put a little bigger number. Let's assume ${\rm j} = 78$. Does "$78$" have any meaning? Nothing in particular. This is my age. The calculation result is as follows.

====== The calculation results are shown below. ======
j = 78
Prime number closest to j (upper) = 79
difference = 1
PrimeQ = True
Enter j for the next search. 

The closest prime number to ${\rm j} = 78$ is "$79$". (Next year my age will be a prime number)

Let's check a slightly larger number. Try:

${\rm j}\,=\,26881171418161354484126255515800135873611119$

This number is ${\rm Round}\, [{\rm E}{\text ^}{100}]$. The calculation result is as follows.

====== The calculation results are shown below. ======
j = 26881171418161354484126255515800135873611119
Prime number closest to j (upper) = 26881171418161354484126255515800135873611287
difference = 168
PrimeQ = True
Enter j for the next search. 

The input integer ${\rm j}$ and the nearest prime number are as follows.

${\rm j}\,=\,26881171418161354484126255515800135873611119$

${\rm A\ prime\ number\ close\ to\ j}\,=\,26881171418161354484126255515800135873611287$

Some calculation examples are shown in the table.

$$\begin{array}{ccc} {\rm j\;\, (Any\ integer)} & {\rm prime\ number\ closest\ to\ j\ (upper)}&{\rm difference}\\ 5 & 5 &0\\ 10 & 11&1 \\ 15 & 17&2 \\ 20 & 23&3 \\ 78 & 79&1 \\ 123 & 127&4 \\ 567 & 569&2 \\ 999 & 1009&10 \\ 54321 & 54323&2 \\ 123456789 & 123456791 &2\\ 5454545454545454 & 5454545454545483&29 \\ 9876543210123456789 & 9876543210123456803&14 \\ 3141592653589793238462643 & 3141592653589793238462773&130 \\ \text{Omitted below} & \text{Omitted below} &\text{Omitted below} \end{array}$$

POSTED BY: Koichi Ohno
2 Replies
Posted 4 years ago

I don't know who you are, but I would like to thank you for improving my program that I posted two years ago.

You defined j, and used Quotient[] and FindInstance[] to find the solution.

I didn't know about Quotient[] and FindInstance[], so this will be helpful for me in the future.

... I'm getting old. I'm getting older, and the months are passing quickly, and I feel like difference>2.

POSTED BY: Koichi Ohno
Posted 4 years ago

Or just use NextPrime[x] :)

POSTED BY: Leponzo _
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard