[Math] Happy New Prime Year!

nt.number-theoryprime numbers

It happens that next year 2011 is prime, while outgoing 2010 is
highly composite in the sense that the number of its distinct prime factors
is 4, maximal possible for a year $< 2310$.

Let me denote by $s(n)$ the number of distinct prime factors of $n$
and note that $s(2011)=1$, $s(2012)=2$ and $s(2013)=3$. I wonder
whether there is a rigorous argument or some heuristic considerations
to show that, for each $k\ge1$, there exist (infinitely many integers)
$n$ satisfying $s(n+1)=1$, $s(n+2)=2$, $\dots$, $s(n+k)=k$.

This can be thought as a generalization of the infiniteness of primes
($k=1$), but I ask this question for curiosity only.

Happy New Prime Year 2011! (Please do not count the exclamation mark as factorial.)

Best Answer

You missed the excitement of 1998, with $1999=1999, 2000=2^4 \cdot 5^3, 2001=3 \cdot 23 \cdot 29,$ and $2002=2 \cdot 7 \cdot 11 \cdot 13$

A quick set of thoughts, too long to fit in a comment:

this requires finding a "prime gap" of length $k-1$, since $s(n+1)=1$ means ~~that $n+1$ is prime~~ that $n+1$ is either prime or a power of a prime, but the next $k-1$ digits are composite since s(n+x)>1 for $2 \le x \le k$. This also means that $s(n+2)=2$ only because $s(n+2)$ is even, thus $2$ is one of the factors and implies that $(n+2)/2$ is prime (or that $(n+2)/2^j$ is prime for some $j \in \mathbb{Z}$), since $n+2$ only has two factors and one of them is $2$ (or $2^j$).

For $s(n+k)$ to have $k$ distinct prime factors means that it has to be at minimum a product of the first $k$ prime numbers, while it definitely has to be a multiple of the product of $k$ prime numbers. So the two key restrictions are that s(n+k) is $k$-composite (has $k$ prime factors) and that both (n+1) and (n+2)/2 are prime numbers.

Hmm, I thought something about the fact that either s(n+2) or s(n+4) would be divisible by $4$ while the other would be divisible by $2$ but not by $4$ would play some role in this.

Here are some quick results from running "bash", "factor", and "sed" and "awk" at the command line:

If you want an ascending run of 1,2, and 3 prime factors, the smallest example starts at $n=63$, with $64=2^6, 65=5 \cdot 13, 66=2 \cdot 3 \cdot 11$

If you want an ascending run of 1,2,3, and 4 prime factors, we already missed the exciting years of $n=1866$ and $n=1998$

1867: 1867
1868: 2 2 467
1869: 3 7 89
1870: 2 5 11 17

1999: 1999
2000: 2 2 2 2 5 5 5
2001: 3 23 29
2002: 2 7 11 13

And the next few years with ascending runs of 1,2,3, and 4 prime factors will start after the years 3216, 4056, and 4176 with 3217, 4057, and 4177 as prime years. Unfortunately, these computational results are not giving me the germ of any shortcut or understanding. There are also some descending sequences in terms of the number of prime factors, and their placement also does not help.

If you want an ascending run of 1,2,3,4, and 5 prime factors, we have to wait almost half-a-million years to get to the exciting years of $n=491850$ and $n=521880$ for $k=5$

491851: 491851
491852: 2 2 122963
491853: 3 19 8629
491854: 2 11 79 283
491855: 5 7 13 23 47

521881: 521881
521882: 2 260941
521883: 3 3 3 3 17 379
521884: 2 2 11 29 409
521885: 5 7 13 31 37

Now with four numbers computed and found, I searched the OEIS and found the corresponding sequence. Since the Online Encyclopedia already has this sequence, I'm hanging up my computational hat and heading off to work. :)

http://oeis.org/A086560

Start of first run of n successive numbers in which i-th number has exactly i distinct prime divisors for i = 1..n
2, 5, 64, 1867, 491851, 17681491, 35565206671
J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 64, p. 23, Ellipses, Paris 2008.

Related Solutions

[Math] Constructing prime numbers

You can obtain a complete heuristic picture of what is going, by supposing that quadratic residues (as suggested by Laurent) are the only likely obstruction to getting the next prime. More precisely, if you let $Q_n = \prod_{k \le n} q_k$ be the product of all of the primes discovered so far, then you can let $p_{n+1} = p$ be the first remaining prime such that $Q_n$ is a quadratic residue mod $p$, assuming Denis' first proposal. Or, assuming Denis' second proposal, you can let $p$ be the first remaining prime such that either $Q_n$ or $-Q_n$ is a quadratic residue mod $p$. (Thus it will simply be the next prime if that prime happens to be 3 mod 4.) Or, assuming that you only use the sum formula, you would only check $-Q_n$. Then experimentally, $q_{n+1} = p_{n+1}$ in all three cases.

This describes the sequence that Charles obtained, which I also obtained (at least the first half of it) with a Sage program.

qseq = [2]
for z in range(16):
    attain = set(); Q = prod(qseq)
    prediction = [p for p in list(primes(500)) if not p in qseq and
        (legendre_symbol(-1,p) == -1 or legendre_symbol(Q,p) == 1)][0]

    for S in Combinations(qseq):
        A = prod(S); attain.update([abs(A-Q/A),A+Q/A])

    best = 10000
    attain.discard(1)
    best = min([min(factor(m))[0] for m in attain])
    print prediction,':',qseq,'->',best
    qseq.append(best)

Assuming both the sum and the difference are used, the validity of this prediction reduces to the following: If $p$ is this next prime, then the question is whether $1$ appears in the set product of the subsets $\{q_k,1/q_k\}$ and $\{\pm 1\}$ in the multiplicative group $(\mathbb{Z}/p)^*$. This is a question in additive set theory if you take a formal logarithm and pass to the additive group $\mathbb{Z}/(p-1)$. A reasonable conjecture is that you are convolving a lot of subsets that don't come close to lying in a subgroup of $\mathbb{Z}/(p-1)$, so you can expect $0$ to appear in the sum. The heuristic has such a large margin that it may be possible with existing methods to prove that it is always so.

The other part of the question is how much you deviate from seeing the primes in order. Again, using a randomness heuristic in number theory, the "probability" that a prime $p$ will be skipped at a given stage is 1/2 (assuming that it is 1 mod 4 in the second case). So you expect the first skipped prime to eventually be included with a "half life" of one round. Thus you expect the sequence to only ever be barely ahead of the list of primes, and you expect $q_n$ to be the $n$th prime infinitely often.

[Math] Proof for new deterministic primality test

@Igor Rivin

I will answer Your question here. I have done a research about safe primes, and I have found a new deterministic primality test for safe primes. This test goes as follows: We have two statements:

1.) Let $p=3$ (mod $4$) be prime. $2p+1$ is also prime if and only if $2p+1$ divides $2^p−1$.

2.) Let $p=1$ (mod $4$) be prime. $2p+1$ is also prime if and only if $2p+1$ divides $2^p+1$.

(Statement 1. is proven by Lagrange 1775, and statement 2. is proven by Batominovsky 2015)

So if a number $N=2\cdot p+1$ holds the congruence $2^p\equiv \pm1\ ($mod $N)$ then it is definitely prime.

From this point I went one step further to $N=p\cdot2^n + 1$.

Best Answer

Related Solutions

[Math] Constructing prime numbers

[Math] Proof for new deterministic primality test

Related Question