3
$\begingroup$

Rowland's sequence, named after Professor Eric Rowland, is defined as:

$$a_1=7$$

$$a_n=a_{n-1}+gcd(n,a_{n-1}), n \gt 1$$

Rowland already proved ("A Natural Prime-Generatin Recurrence", Journal of Integer Sequences, Vol.11, 2008, Article 08.2.8) that for any index $n$ of the sequence, the difference $a_{n}-a_{n-1}$ is a prime number or $1$.

I would like to ask about an observation regarding Rowland's sequence, that might be a new property of the sequence. I found it just by trial and error, but as far I have tested it, it seems to be true up to index $i=498270791$ (after that point the computer calculations are very slow). The questions are at the end of the explanation.

Basically the observation is (Expression $1$):

$$\forall i \ge 2, \ \exists j \gt i \ :\ \lfloor \frac{lcm(1..i)}{a_i} \rfloor \lt a_j \ \ ,\ \ j \in \Bbb P$$

$$ \land \not \exists k \lt j \ :\ \lfloor \frac{lcm(1..i)}{a_i} \rfloor \lt a_k$$

In other words, any $a_i$ ($i \ge 2)$ of the sequence seems to be a kind of "witness" or "marker" of a greater element of the sequence, $a_j$, whose index $j$ is always a prime number. Here is the method of calculation:

  1. We take any index $i \ge 2$, and calculate the least common multiple of all the natural numbers up to the index: $lcm(i)$.

  2. Then we divide $lcm(i)$ by the current element of the sequence ${a_i}$.

  3. Our witness will be the floor of the number resulting of the division at step $2$.

  4. Now we look for the first element $a_j$ of Rowland's sequence greater than the witness of step $3$ (the index $j$ is also greater than $i$).

  5. The index of that number, $j$, seems to be always a prime number.

For instance here is the list of the first $27$ primes confirmed by this method (in other words, the index $j$ that is found and is always prime). Some of them are repeated, for instance $2$ and $47$, because for those cases lcm([1..i])=lcm([1..i+1]) and the floor of the division in those cases is always smaller than the same $a_j$, and thus the index $j$ is the same prime number:

enter image description here

Another way to write the (Expression $1$) is using the second Chebyshev function, which is exactly the natural logarithm of the least common multiple of the integers from $1$ to $n$, so for that reason we can write as follows (Expression $2$):

$$lcm(1..n)=e^{\psi(n)}$$

$$\forall i \ge 2, \ \exists j \gt i \ :\ \psi(i)-log(a_i) \lt log(a_j)\ ,\ \ j \in \Bbb P$$

$$ \land \not \exists k \lt j \ :\ \psi(i)-log(a_i) \lt log(a_k)$$

or

$$\forall i \ge 2, \ \exists j \gt i \ :\ \sum_{p^t \le i} p-log(a_i) \lt log(a_j)\ ,\ \ j \in \Bbb P$$

$$ \land \not \exists k \lt j \ :\ \sum_{p^t \le i} p-log(a_i) \lt log(a_k)$$

This is the PARI\GP code, please feel free to use it and modify it:

\p200000;
print();print("Calculating first 30 Rowland's witnesses:");print();testlimit = 30;current_rowland_seq_element=7;lcm_list=listcreate();listput(lcm_list,1);witnesses_list=listcreate();for(sequence_index=2,testlimit,current_rowland_seq_element=current_rowland_seq_element+gcd(sequence_index,current_rowland_seq_element);listput(lcm_list,sequence_index);listput(witnesses_list,truncate(lcm(lcm_list)/current_rowland_seq_element)););print(witnesses_list);print();print("Starting test:");print();sequence_index=2;current_rowland_seq_element=7;testlimit = 31247916400;was_found_prime=0;for(prospect=1,length(witnesses_list),if(witnesses_list[prospect]>testlimit,break);while(1,if(was_found_prime==0,current_rowland_seq_element=current_rowland_seq_element+gcd(sequence_index,current_rowland_seq_element),was_found_prime=0);if(current_rowland_seq_element>witnesses_list[prospect],print("(timer:",getabstime(),")\tThe index of the closest element of Rowland's sequence greater than:\t",witnesses_list[prospect],"\t is:\t",sequence_index,"\t . Primality test of the index (0=False, not prime / 1:True, is prime). Result:\t",isprime(sequence_index));print();was_found_prime=1;break;);sequence_index=sequence_index+1;););

It seems quite interesting, but still do not know if there is a counterexample or not. My computer is quite slow, and the calculation of the next prime index will take it around $6$ hours (probably my computer will run out of memory, but I am trying).

I would like to ask the following questions:

  1. Is there a counterexample? If somebody reading this wants to use the PARI\GP code or create a quicker version in another language and try to look for a counterexample would be great. Maybe the observation does not hold for the next still not calculated indexes of the sample list of the picture and included in the PARI\GP code as well.

  2. If there is not a counterexample, why is $a_i$ able to be the witness of a greater $a_j$ whose index $j$ is prime? It might be related with the relationship between the recurrence relation used by Rowland's sequence, which is based on the manipulation of the greatest common divisor, gcd, versus the value lcm($[1,i]$). The link of the expression with the second Chebyshev function is also interesting because it is very related with the primes in the interval $[1,i]$.

Maybe the reason is very straightforward but I cannot see it. Any insights are very appreciated, thank you!

$\endgroup$
  • 1
    $\begingroup$ The $ lcm(1..i)$ called in a loop with consecutive increasing $i$ is extremely expensive when $i$ goes over -say- $100$ or $1000$. It is better to introduce a new variable $q=1$ and then for each loop write $ q=lcm(q,i) ; $ $\endgroup$ – Gottfried Helms Mar 31 '17 at 9:03
  • $\begingroup$ @GottfriedHelms that is true! I will fix it on Monday and will update the content. Thank you! $\endgroup$ – iadvd Mar 31 '17 at 10:14
  • 2
    $\begingroup$ Iadvd, sorry to have found the first counterexample at $ i_1 = 29$ , $ a_1= 77 $ with $: a_2 = 30247916401 $ at index $ i_2 = 14303242639 $ index $i_2 $ +++ is not prime $\endgroup$ – Gottfried Helms Apr 2 '17 at 1:22
3
$\begingroup$

not an answer, just a contribution how to improve the Pari/GP-code

Update: found a counterexample (not prime)

I think this is an improvement of your routine. It avoids completely the memory-consuming lists and implements the search by the trick of comparing in two parallel Rowlands-sequences $a_1$ and $a_2$ where $a_2$ proceeds faster and always as far as it is smaller or equal than the criterion $c_1$ from the first sequence, and prints the first $a_2$ when it is greater. Then it looks for the next $a_1$ such that its criterion $c_1$ is greater than the last displayed $a_2$.
Hmm, also I need much more moderate real-float precision. My default is \p200 and even smaller might be still functional. Your very large $\p200000 $ should be superfluous and should consume exorbitant time too...

\p 30                     \\ this decimal real-precision seems sufficient!
txt=["+++ is not prime","is prime"]; \\ as markers for your conjecture
resultsloop_max=22;       \\ number is not even exhausted given the loop2_max!
loop1_max = 100;          \\ maximal distance of consecutive a_1 displayed
loop2_max = 100 000 000;  \\ sequence 2 is taken maximally loop2_max forward.
                          \\ makes sure we do not run into gigantic numbers/time
            \\ begin of the loops
{gettime();          \\ reset time-counter     
a1  = a2 =7;         \\ current elements of the Rowlands-sequences a1 and a2
i1  = i2 =1;         \\ consecutive indexes for the two running sequences
c1  =     1/a1;      \\ criterion needed only for the first running sequence
lcm1=     1;         \\ lcm       needed only for the first running sequence

for(j=1,resultsloop_max,      \\ we'll have at most ... lines of protocol
                 \\ the following loop makes sure we display only such
                 \\ lines where the a_2 to be displayed are all different
   for(k=1,loop1_max,       
           i1++; a1+=gcd(a1,i1);
             lcm1=lcm(lcm1,i1); c1=1.0 * lcm1 / a1;
         if(c1>a2,break());
       ); 
   found=0;     \\ if in the following loop nothing is found, exit all loops
   for(k=1,loop2_max,
       i2++; a2+=gcd(a2,i2); if(a2 <= c1, next());
       print(i1 ,"   ",a1,"   ",c1," : ",
             a2 ,"   ",i2,"   ",      txt[1+isprime(i2)," time used:", round(gettime()/1000.0)," secs"]);
       found=1; break(); 
       );
   if(!found, break());    \\ nothing found in the next interval of loop2_max
 );
secs = round(gettime()/1000);
print("time used:",secs, " secs" ); }

This gives (except the header and small improvements in formatting colums):

i1   a1   c1            :       a2           i2      comment
------------------------+-----------------------------------------------  
 7   19            22.1 :          33           11   is prime
 8   20            42   :          43           19   is prime
 9   21           120   :         141           47   is prime
11   33           840   :         841          373   is prime
13   37          9739.4 :       11337         3779   is prime
16   40         18018   :       22677         7559   is prime
17   41        298835.1 :      364209       121403   is prime
19   43       5413780.5 :     5836947      1945649   is prime  (3 secs)
23   69      77597520.  :    93418683     31139561   is prime  (54 secs)
25   73   3.6672801 E8  :   373678827    124559609   is prime  (170 secs) 
27   75   1.0708458 E9  :  1494812373    498270791   is prime  (683 secs)
29   77   3.0247916 E10 : 30247916401  14303242639   +++ is not prime  (28052.900 secs) 
(stopped after finding) 

[update]: The counterexample at $i_1=29,a_1=77$ was found using loop2_max=100 000 000 000 after 28052.900 secs ( = 7 3/4 hours)

$\endgroup$
  • $\begingroup$ I appreciate this very much! I will give it a long run on Monday, hopefully I will be able to obtain one or two more indexes. $\endgroup$ – iadvd Mar 31 '17 at 11:21
  • $\begingroup$ thank you very much for the time you took for test it. I have learnt new ways of enhancing PARI/GP through your explanations! $\endgroup$ – iadvd Apr 2 '17 at 2:15
  • 1
    $\begingroup$ @iadvd : you're welcome! It would have been nice if we had indeed had a new prime-creator here, now so... anyway it has been a nice experiment on an interesting sequence - thanks for this. $\endgroup$ – Gottfried Helms Apr 2 '17 at 5:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.