# Prime Number Sieve using LCM Function

How to prove following conjecture ?

Definition :

Let $b_n=b_{n-2}+\operatorname{lcm}(n-1 , b_{n-2})$ with $b_1=2$ , $b_2=2$ and $n>2$ .

Let $a_n=b_{n+2}/b_n-1$

Conjecture :

1. Every term of this sequence $a_i$ is either prime or $1$ .

2. Every odd prime number is member of this sequence .

3. Every new prime in sequence is a next prime from the largest prime already listed .

Maxima implementation of sieve :

/* input number n */
n:200;
b1:2;
b2:2;
max:2;
k:3;
i:1;
while max<=n do (
if i=1 then(
print(max),
i:0
),
b3:b1+lcm(k-1,b1),
a:b3/b1-1,
k:k+1,
b1:b2,
b2:b3,
if max<a then (
max:a,
i:1
)
);


You can run this code here .

• The $b_n$ are actually two independent sequences: $$\\ b_{n}=b_{n-1}+\text{lcm}(2n-1,b_{n-1}), n \ge 2, b_1 =2, \text{former even indexes} \\ b_{n}=b_{n-1}+\text{lcm}(2n-2,b_{n-1}), n \ge 2, b_1=2, \text{former odd indexes}$$ a similar sequence: $$b_n = b_{n-1} + \text{lcm}(n,b_{n-1}), n\ge 2, b_1=1$$ oeis.org/A135504 , oeis.org/A217663 – miracle173 Jan 1 '15 at 10:28

This is sequence A135506 in OEIS, and as far as I know, no proof to conjecture 1 has been published. Benoit Cloitre announced one in this paper, but I don't think it's been published.

Conjecture 2 is actually very simple to proof, I did so in my bachelor's thesis. Unfortunately, this is only in German, I can write it up in English if you're interested.

I think conjecture 3 is pretty much a direct consequence from the fact that $a_p=p$ for every prime, and this is the first time $p$ can occur in the sequence.

Edit: I actually realised that your definition of the quotient is slightly different since it goes two steps back. I'll check the argument - it shouldn't make much of a difference.

Edit: This is the full argument for conjectures 2 & 3. First we need the general relation between gcd $(a,b)$ and lcm $[a,b]$:

$$a\cdot b = (a,b)\cdot[a,b].$$

Then we note that the lowest common multiple $[n-1,b_{n-2}]$ is in particular a multiple of $b_{n-2}$, say $kb_{n-2}$ with $1\le k\le n-1$. Hence we have

$$b_n=b_{n-2}(k+1),$$

so in every step the term $b_n$ gets a new factor between $2$ and $n$ which means in particular that all prime factors of $b_n$ are less or equal to $n$.

Now we rearrange $a_n$ with the above observation to

$$a_n=\frac{n+1}{(n+1,b_n)}.$$

Let $p$ be a prime. Then $(p,b_{p-1})=1$ since all prime factors of $b_{p-1}$ are strictly smaller than $p$. But then

$$a_{p-1}=\frac{p}{(p,b_{p-1})}=p$$

as claimed in conjecture 2.

Further, we have obviously $a_n\leq n+1$ for all $n$, so the first index for which the prime $p$ can appear in the sequence is $p-1$ which immediately implies conjecture 3.

As mentioned before, conjecture 1 seems quite a bit more difficult and I'd be interested in a proof myself.

PS: It took me a couple of pages to prove these facts when I first worked on them 6 years ago, but it's clearly much simpler now that I thought about it again.