This site is supported by donations to The OEIS Foundation.

Decomposition into weight * level + jump

From OeisWiki

Jump to: navigation, search


Contents

Decomposition of numbers into weight * level + jump

The main goal of this page is to provide a new way to see certain numbers by their decomposition into weight * level + jump. This decomposition can be seen as a generalization of the sieve of Eratosthenes (which is the particular case of the sequence of natural numbers). Applied to prime numbers, this decomposition is used to obtain a new classification of primes.

Principles

Principle of decomposition: we choose the smallest weight such that in the Euclidean division of a number by its weight, the remainder is the jump (first difference, gap). The quotient will be the level.

Principles of classification: if the number is not decomposable, it is not classified. If the weight is greater than the level then the number is classified by level, if not then it is classified by weight.

Definitions

Let \scriptstyle {\{a(n)\}}_{n=i_\min}^{\infty} \, be a strictly increasing integer sequence.

Jump

The jump (first difference, gap) of \scriptstyle a(n) \, is defined as

d(n) := a(n+1) - a(n). \,

l(n)

l(n) is defined as

l(n) := 
\begin{cases} a(n) - d(n) & \text{if } a(n) - d(n) > d(n), \\ 0 {\rm ~otherwise}. \end{cases} \,

Alternative definition with mod function

l(n) :=  {\rm largest~} l {\rm~such~that~} a(n+1) = a(n) + a(n){\rm~}mod{\rm~}l, {\rm~or~} 0 {\rm~if~no~such~} l {\rm~exists.~}

Weight

The weight of \scriptstyle a(n) \, is defined as

k(n) := 
\begin{cases} {\rm smallest~} k > d(n) {~s.t.~} k|l(n), \\ 0 {\rm ~if~} l(n) = 0. \end{cases} \,

Alternative definition with mod function

k(n) :=  {\rm smallest~} k {\rm~such~that~} a(n+1) = a(n) + a(n){\rm~}mod{\rm~}k, {\rm~or~} 0 {\rm~if~no~such~} k {\rm~exists.~}

Level

The level of \scriptstyle a(n) \, is defined as

L(n) := 
\begin{cases} \frac{l(n)}{k(n)} & \text{if } k(n) > 0, \\ 0 & \text{if } k(n) = 0. \end{cases} \,

Decomposition criterion

A strictly increasing integer sequence, \scriptstyle {\{a(n)\}}_{n=i_\min}^{\infty} \, can be decomposed into weight * level + jump when \scriptstyle l(n) \, is different from 0 which can be rewritten when:

a(n) - d(n) > d(n), \,

or

d(n) < \frac{1}{2} \cdot a(n), \,

or

 a(n+1) < \frac{3}{2} \cdot a(n) \,

The weight \scriptstyle k(n) \, is the smallest such that in the Euclidean division of \scriptstyle a(n) \, by its weight \scriptstyle k(n) \,, the quotient is the level \scriptstyle L(n) \,, and the remainder is the jump \scriptstyle d(n) \,. We have the unique decomposition

a(n) = k(n) \cdot L(n) + d(n) = {\rm weight} \cdot {\rm level} + {\rm jump} \,

Principles of classification

  • If for \scriptstyle a(n) \,,
l(n) = k(n) = L(n) = 0 \,

then \scriptstyle a(n) \, is not classified.

  • If for \scriptstyle a(n) \,,
k(n) > L(n) \,

then \scriptstyle a(n) \, is classified by level, if not then it is classified by weight.

Algorithms

File:Decomp algo.jpg

Naive algorithm (PARI/GP):

decompnaive(n,n1)={
	/*strictly increasing*/
	if(n>=n1,print("n1 must be greater than n");return);
	/*jump*/
	d=n1-n;
	/*l=n-d if n>2*d else the number is not decomposable*/
	if(n>2*d,l=n-d,print(d, ", 0, 0");return);
	/*we look for the weight to jump+1 until l*/
	for(k=d+1,l,if(n%k==d,print(n," = ",k," * ",l/k," + ",d);return));
}

Algorithm "newSieve":

decompsieve(n,n1)={
	/*strictly increasing*/
	if(n>=n1,print("n1 must be greater than n");return);
	/*jump*/
	d=n1-n;
	/*l=n-d if n>2*d else the number is not decomposable*/
	if(n>2*d,l=n-d,print(d, ", 0, 0");return);
	/*we look for the weight to jump+1 until sqrt(l)*/
	for(k=d+1,sqrt(l),if(n%k==d,print(n," = ",k," * ",l/k," + ",d);return));
	/*we look for the level to jump until 1 (--)*/
	forstep(le=d,1,-1,if(n%floor(l/le)==d,print(n," = ",l/le," * ",le," + ",d);return));
}

Algorithm "newSieve" is the fastest for numbers classified by level.

General remarks

\scriptstyle n Numbers of decompositions into weight * level + jump
1 0
2 0
3 1
4 1
5 2
6 2
7 3
8 3
9 4
10 4
11 5
... ...

The numbers of decompositions possible of \scriptstyle n into weight * level + jump is A004526 (with an offset at 1).

The sequence with the the greatest growth that can be decomposed is A003312.

Throughout this page, the jump is the first difference but we can take the second, third... difference. See A133346 and A133347 for primes.

Decomposition of natural numbers, the sieve of Eratosthenes

If the decomposition is possible (i.e. if n > 2), we have:

The weight is the smallest prime factor of \scriptstyle n-1 \, and the level is the largest proper divisor of \scriptstyle n-1 \,. The decomposition into weight * level + jump of natural numbers is thus a reformulation of the sieve of Eratosthenes.

Plot of log(A020639) vs log(A032742) for n ≤ 10^4, the sieve of Eratosthenes (OEIS graph):

File:Natural class.png

Decomposition of prime numbers

\scriptstyle p(1) \,=\, 2 , \scriptstyle p(2) \,=\, 3 and \scriptstyle p(4) \,=\, 7 are the only primes not decomposable[1]. Except for \scriptstyle p(1) \,=\, 2 , \scriptstyle p(2) \,=\, 3 and \scriptstyle p(4) \,=\, 7 , the decomposition into weight * level + jump of prime numbers is:

Plot of log(A117078) vs log(A117563) for n ≤ 10^4 (OEIS graph):

File:Primes_class.png‎

A classification of primes connected to the OEIS

File:Primes_class_connectOEIS.jpg

Primes of level (1;i)

Principle of classification for primes of level 1:

If for p(n), l(n) is a prime says prime(n-i) then p(n) is of level (1;i).

Direct relations

For \scriptstyle p(n) \, different from 2, 3 and 7, we have:

  • l(n) = p(n) - g(n) = 2 \cdot p(n) - p(n+1) = k(n) \cdot L(n), \,
  • p(n) = l(n) + g(n) = k(n) \cdot L(n) + g(n), \,
  • \gcd(g(n),2) = 2, \,
  • \gcd(p(n),g(n)) = \gcd(p(n) - g(n),g(n)) = \gcd(l(n),g(n)) = \gcd(L(n),g(n)) = \gcd(k(n),g(n)) = 1, \,
  • 3 \le k(n) \le l(n), \,
  • 1 \le L(n) \le l(n) / 3, \,
  • 2 \le g(n) \le k(n) - 1, \,
  • 2 \cdot g(n) + 1 \le p(n). \,

Primes classified by weight

For primes classified by weight (Cf. A162175) (primes for which \scriptstyle k(n) \,\le\, L(n) \,), we have:

  • g(n) + 1 \le k(n) \le \sqrt{l(n)} \le L(n) \le \frac{l(n)}{3}. \,

82,89 % of primes \scriptstyle p(n) \, are classified by weight for \scriptstyle n \le 5 \cdot 10^7 \,.

We can see that by definition, the primes classified by weight follow Legendre's conjecture and Andrica's conjecture.

Primes classified by level

For primes classified by level (Cf. A162174) (primes for which \scriptstyle k(n) \,>\, L(n) \,), we have:

  • L(n) < \sqrt{l(n)} < k(n) \le l(n), \,
  • L(n) + 2 \le g(n) + 1 \le k(n) \le l(n). \,

17,11 % of primes \scriptstyle p(n) \, are classified by level for \scriptstyle n \le 5 \cdot 10^7 \,.

Knowing that the primes are rarefying among the natural numbers, we make the following conjecture:

Lesser of twin primes

If \scriptstyle p(n) is a lesser of twin prime greater than 3 then \scriptstyle p(n) has a weight of 3. If \scriptstyle p(n) has a weight of 3 then \scriptstyle p(n) is a lesser of twin prime greater than 3[1].

Conjectures

The well-known conjecture on the existence of an infinity of twin primes can be rewritten as:

  • Conjecture 1: The number of primes with a weight equal to 3 is infinite.

To extend this conjecture we make these two conjectures:

  • Conjecture 2: The number of primes with a weight equal to k is infinite for any \scriptstyle k \,\ge\, 3 \, which is not a multiple of 2;
  • Conjecture 3: The number of primes of level \scriptstyle L \, is infinite for any \scriptstyle L \,\ge\, 1 \, which is not a multiple of 2.

 

  • Conjecture 4: Except for p(6) = 13, p(11) = 31, p(30) = 113, p(32) = 131 et p(154) = 887, primes which are classified by level have a weight which is itself a prime.


  The conjecture on the existence of an infinity of balanced primes can be rewritten as:

That we can easily generalize by:

 

  • Conjecture 7: If the jump g(n) is not a multiple of 6 then l(n) is a multiple of 3.
  • Conjecture 8: If l(n) is not a multiple of 3 then jump the g(n) is a multiple of 6.


  Knowing that the primes are rarefying among the natural numbers, we make the following conjecture:

Decomposition of odd numbers

If the decomposition is possible, we have:

Plot of log(A090368) vs log(A184726) for n ≤ 10^4 (OEIS graph):

File:Odd_class.png

Decomposition of even numbers

If the decomposition is possible, we have:

Plot of log(A090369) vs log(A184727) for n ≤ 10^4 (OEIS graph):

File:Even_class.png

Decomposition of composite numbers

If the decomposition is possible, we have:

Plot of log(A130882) vs log(A179621) for n ≤ 10^4 (OEIS graph):

File:Composite_class.png

Decomposition of semiprimes

If the decomposition is possible, we have:

Plot of log(A130533) vs log(A184729) for n ≤ 10^4 (OEIS graph):

File:semiclass.png

Decomposition of 3-almost primes

If the decomposition is possible, we have:

Plot of log(A130650) vs log(A184753) for n ≤ 10^4 (OEIS graph):

File:3alPrimesclass.png

Decomposition of lucky numbers

If the decomposition is possible, we have:

Plot of log(A130889) vs log(A184828) for n ≤ 10^4 (OEIS graph):

File:Luckyclass.png

Decomposition of prime powers

If the decomposition is possible, we have:

Plot of log(A184829) vs log(A184831) for n ≤ 10^4 (OEIS graph):

File:Ppower_decomp.png

Decomposition of squarefree numbers

If the decomposition is possible, we have:

Plot of log(A184832) vs log(A184834) for n ≤ 10^4 (OEIS graph):

File:Squarefree_decomp.png

Decomposition of triangular numbers

If the decomposition is possible, we have:

Plot of log(A130703) vs log(A184219) for n ≤ 10^4 (OEIS graph):

File:Triangclass.png

Decomposition of squares

If the decomposition is possible, we have:

Plot of log(A133150) vs log(A184221) for n ≤ 10^4 (OEIS graph):

File:Squareclass.png

Decomposition of pentagonal numbers

If the decomposition is possible, we have:

Plot of log(A133151) vs log(A184751) for n ≤ 10^3 (OEIS graph):

File:Penta_class.png

Sequences

Sequences related to the decomposition.

See also

Notes

  1. 1.0 1.1 Rémi Eismann, arXiv:0711.0865 (pdf) [1]

External links

Personal tools