[seqfan] Re: Theorem -- Extension to negative bases

[Andrew N W Hone]

Dear Thomas, 

Just a few comments on your discussion.

It makes sense to denote the set as B(b), to indicate the dependence on b.

The aforementioned proof of the theorem that 

n belongs to B(b) if and only if N=(b^n-1)/(b-1) belongs to B(b) 

is equally valid for negative b. (Note also that n belongs to B(-b) if and only if it belongs to B(n-b).)

In fact the definition of the set is equivalent to the following:

n belongs to B(b) if and only if b^n == b (mod n) and gcd(b-1,n)=1.

Also the original definition of the set can be stated without division, as 

n belongs to B(b) if and only if b^{n-1}+b^{n-2}+...+ b == 0 (mod n), 

and the latter two definitions are valid for any integer b.

So the set B(b) is the union 

B(b) = { primes } \cup { pseudoprimes to base b } \cup { divisors of b }, 

where the pseudoprimes are the composite n such that b^{n-1} - 1 == 0 (mod n).

The case of B(0) is trivial: it consists of all natural numbers. 

With the above alternative definitions, the set B(1) is also defined: it is a set with just one element, {1}.

The set B(-1) consists of all odd natural numbers.

So the only interesting cases are when |b|>1.

For a fixed b, it might be interesting to look for pseudoprimes by using the above theorem. For example, starting from any divisor of b, n_0>1, one can recursively construct 

n_{j+1} = (b^{n_j}-1)/(b-1), 

for j=0,1,2,... It is easy to see that gcd(n_j,b)=1 for j>=1. Similarly one can start with n_0 any prime. Many of the terms n_j will be prime, but sometimes pseudoprimes appear. I don't know what proportion of terms in the sequence goes between prime/pseudoprime, but it might be interesting to find out.

Example 1: for b=2, start with n_0=2, then n_1=3, n_2=7, n_3=127, n_4=2^{127}-1 are all (Mersenne) primes. Where does the first pseudoprime appear? (This can be checked quickly with the Lucas-Lehmer test.) 

Example 2: for b=3, start with n_0=3, then n_1=121 (pseudoprime to base 3), n_2 = (3^{121}-1)/2 is another pseudoprime (it is divisible by 23); can one say anything about whether subsequent terms are prime or not?

Anyway, it looks quite fun, and may lead to some new sequences!

All the best,
Andy 
 


________________________________________
From: SeqFan [seqfan-bounces at list.seqfan.eu] on behalf of Tomasz Ordowski [tomaszordowski at gmail.com]
Sent: 19 April 2018 10:19
To: Sequence Fanatics Discussion list
Subject: [seqfan] Theorem -- Extension to negative bases

Dear SeqFans!

Let me remind you of the proven generalization:

Let B be the set of natural numbers n such that

      (b^n-1)/(b-1) == 1 (mod n)

with a fixed integer b > 1.

Then, the number (b^k-1)/(b-1) belongs to the set B
if and only if k belongs to B.

The questions: How to extend this theorem to the integer bases b < -1 ?
It should work with every integer b <> 1.  How will it be for b = 0 and -1
?
Is it necessary to assume that n is odd for b < -1 ?

Best regards,

Thomas

P.S. A comment:
  http://oeis.org/A015919
If 2^k-1 is a term, then so is k.
Asymptotic formula: a(n) ~ n log n.
I still have a full account on the OEIS.



<#m_-1301679863165878748_m_-8214366375184677225_m_8821574979675864549_DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2>

--
Seqfan Mailing list - http://list.seqfan.eu/