cp's OEIS Frontend

The generalized Lucas sequences of integer parameters (a,b) defined by U(m+2)=a*U(m+1)-b*U(m) and U(0)=0, U(1)=1, satisfy the identity

U(p-J(p,D)) == 0 (mod p) when p is prime, b=1 and D=a^2-4.

This sequence contains the odd composite integers with U(m-J(m,D)) == 0 (mod m).

For a=7 and b=1, we have D=45 and U(m) recovers A004187(m).

For primes p, m^(2^v(p-1)+1) == -m (mod p) has only one solution m == 0 (mod p). This sequence gives that composite numbers that satisfy this condition.

All terms are odd since for even k, m == -1 (mod k) is a solution.

Odd composite k is a term if and only if v(p-1) <= v(k-1) for all prime factors p of k. Proof: Let k = (p_1)^(e_1)*(p_2)^(e_2)*...*(p_r)^(e_r) be an odd number. m^(2^v(k-1)+1) == -m (mod k) has only one solution if and only if m^(2^v(k-1)+1) == -m (mod (p_i)^(e_i)) has only one solution for 1 <= i <= r, or equivalently, m^(2^v(k-1)) == -1 (mod (p_i)^(e_i)) has no solution for 1 <= i <= r, or v(p_i-1) <= v(k-1) for 1 <= i <= r.

All prime powers of the form p^e for odd prime p and e >= 2 are terms. All Carmichael numbers (A002997) are also terms: if k is a Carmichael number, then p-1 | k-1 for all prime factors p.

Sorting by k/2^bigomega(k) would give the same sequence.

It appears that this sequence can be used to approximate the imaginary parts of the nontrivial zeta zeros, that is, A002410(n) is roughly equal to 2*Pi*a(n)/2^bigomega(a(n)) - n/2 + sqrt(n)/2.

Calculations show that the relative error approaches 1.0+-0.005 for the first 3800 zeros (z=2000 in Mathematica code). For further zeros, a better approximation may be useful, e.g. 2*Pi*a(n)/2^bigomega(a(n)) - n/2 + (1/Pi) * n/log(n+1) +- (...).

By definition, the sequence contains all odd perfect numbers, and also includes any hypothetical odd triperfect number that is not a multiple of 3 (see A005820 and A347391), and similarly, any odd term of A046060 that is not a multiple of 5, etc. If there are no squares in this sequence (see conjecture in A386424), then the latter categories of numbers certainly do not exist, and this is then a subsequence of A228058.

The first nondeficient term is a(32315) = 81022725. See A386426.

Previous name was: phi(a(n)) and (a(n) - 1) have a common factor but are distinct.

Equivalently, numbers n that are Fermat pseudoprimes to some base b, 1 < b < n. A nonprime number n is a Fermat pseudoprime to base b if b^(n-1) = 1 (mod n). Cf. A181780. - Geoffrey Critzer, Apr 04 2015

A071904, the odd composite numbers, is a subset of this sequence. - Peter Munn, May 15 2017

Lehmer's totient problem can be stated as finding a number in this sequence such that gcd(a(n) - 1, phi(a(n))) = phi(n). By the original definition of this sequence, such a number (if it exists) would not be in this sequence. - Alonso del Arte, Sep 07 2018, clarified Sep 14 2018

Because 2 is the only even prime, it implies that, apart from a(2)=3, odd numbers occur in odd positions only (along with many even numbers that also occur in odd positions). This in turn implies that each odd composite (A071904) resides in a separate infinite cycle in this permutation, except 9, which is in a finite cycle (2 3 9 4).

Here oddprime(n) = n-th odd prime = A065091(n) = A000040(n+1), not_an_oddprime(n) = n-th natural number which is not an odd prime = A065090(n).

This sequence can be represented as a binary tree. Each left hand child is produced as A065090(1+n), and each right hand child as A065091(n), when a parent contains n >= 1:

|

...................1...................

2 3

4......../ \........5 6......../ \........7

/ \ / \ / \ / \

/ \ / \ / \ / \

/ \ / \ / \ / \

8 11 9 13 10 17 12 19

14 23 18 37 15 29 21 43 16 31 26 61 20 41 28 71

etc.

Because all odd primes are odd, it means that even terms can only occur in even positions (together with odd composites, A071904, for each one of which there is a separate infinite cycle), while terms in odd positions are all odd.

The terms 9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, ... will never appear in the sequence; they form A071904, the "Odd composite numbers".

Let A = set of numbers of form 6n + 1, B = numbers of form 6n - 1. Eliminating numbers of form 25 + 30s from A and those of form 35 + 30s from B we obtain sets A* and B*. Removing all terms of the sequence from the union of A* and B*, only prime numbers remain. - Hisanobu Shinya (ilikemathematics(AT)hotmail.com), Jul 14 2002

Divide n by a*b*c where a = 2^(A001511(n)-1), b = 3^(A051064(n)-1) and c = 5^(A055457(n) -1). Then the resulting sequence includes only primes and a(n). - Alford Arnold, Sep 08 2003

Composite numbers not divisible by 2, 3 or 5. - Lekraj Beedassy, Jun 30 2004

Composite numbers k such that k^4 mod 30 = 1. - Gary Detlefs, Dec 09 2012

Composite numbers congruent to 1, 7, 11, 13, -13, -11, -7, -1 (mod 30). Since asymptotically, 100% of integers are composite, we have a(n)/n ~ 30/phi(30) = 30/8 = 3.75. - Daniel Forgues, Mar 16 2013

"John [Conway] recommends the more refined partition [of the positive numbers]: 1, prime, trivially composite, or nontrivially composite. Here, a composite integer is trivially composite if it is divisible by 2, 3, or 5." See link to (van der Poorten, Thomsen, and Wiebe; 2006) pp. 73-74. - Daniel Forgues, Jan 30 2015, Feb 04 2015

For the eight congruences coprime to 30, we can use one byte to encode the "primality/non-primality (unit or composite)" for each [30*n, 30*(n+1)[, n >= 0, closed-open interval, either as little endian binary sequence {01111111, 11111011, 11110111, 01111110, ...}, or as big endian binary sequence {11111110, 11011111, 11101111, 01111110, ...}, which we may then express in base 10. - Daniel Forgues, Feb 05 2015