login
Primes of the form m = b^i + b^j - 1, where i > j > 0, b > 1.
7

%I #17 Nov 02 2014 12:18:37

%S 5,11,17,19,23,29,41,47,67,71,79,83,89,107,109,131,149,181,191,239,

%T 251,257,263,269,271,349,379,383,419,461,599,701,809,811,929,971,991,

%U 1009,1031,1039,1087,1151,1259,1279,1301,1451,1481,1511,1559,1721,1871,1979,2063,2069,2111,2161,2213,2267,2351,2549,2861,2939,2969,3079,3191,3389

%N Primes of the form m = b^i + b^j - 1, where i > j > 0, b > 1.

%C If m is a term, then there is a base b > 1 such that the base-b representation of m has digital sum = 1 + j*(b-1) == 1 (mod (b-1)).

%C The base b for which m = b^i + b^j - 1 is not uniquely determined. Example: 11 = 2^3+2^2-1 = 3^2 +3^1-1.

%C Numbers m which satisfy m = b^i + b^j - 1 with odd i and j and b == 2 (mod 3) are not terms. Example: 12189 = 23^3 + 23^1 - 1 is not a prime.

%H Hieronymus Fischer, <a href="/A239709/b239709.txt">Table of n, a(n) for n = 1..10000</a>

%e a(1) = 5, since 5 = 2^2 + 2^1 - 1 is prime.

%e a(2) = 11, since 11 = 2^3 + 2^2 - 1 is prime.

%e a(6) = 29, since 29 = 3^3 + 3^1 - 1 is prime.

%e a(10^1) = 71.

%e a(10^2) = 13109.

%e a(10^3) = 9336079.

%e a(10^4) = 2569932329.

%e a(10^5) = 455578426189.

%e a(10^6) = 68543190483641.

%o (Smalltalk)

%o A239709

%o "Answers the n-th term of A239709.

%o Iterative calculation using A239709_termsLTn.

%o Usage: n A239709

%o Answer: a(n)"

%o | n terms m |

%o terms := SortedCollection new.

%o n := self.

%o m := (n prime // 2) squared.

%o terms := m A239709_termsLTn.

%o [terms size < n] whileTrue:

%o [m := 2 * m.

%o terms := m A239709_termsLTn].

%o ^terms at: n

%o "Remark: A last line of

%o ^terms copyFrom: 1 to: n

%o answers an array of the first n terms"

%o [by_Hieronymus Fischer_, Apr 14 2014]

%o -----------

%o (Smalltalk)

%o A239709_termsLTn

%o "Answers all the terms of A239709 which are < n.

%o Direct processing by scanning the scanning the bases b in increasing order, up to b = sqrt(n), and calculating the numbers b^i + b^j - 1.

%o Usage: n A239709_termsLTn

%o Answer: #(5 11 17 19 23 ...) [terms < n]"

%o | bmax p q n m terms a |

%o terms := OrderedCollection new.

%o n := self.

%o bmax := n sqrtTruncated.

%o 2 to: bmax

%o do:

%o [:b |

%o m := 1 + (n floorLog: b).

%o p := b.

%o 2 to: m

%o by: 1

%o do:

%o [:i |

%o p := b * p.

%o q := b.

%o 1 to: i - 1

%o by: 1

%o do:

%o [:j |

%o a := p + q - 1.

%o a < n ifTrue: [a isPrime ifTrue: [terms add: a]].

%o q := b * q]]].

%o ^terms asSet asArray sorted

%o [by_Hieronymus Fischer_, Apr 14 2014]

%o -----------

%o (Smalltalk)

%o A239709nTerms

%o "Alternative version: Answers the first n terms of A239709. Direct calculation by scanning the numbers b^i + b^j - 1 in increasing order.

%o Usage: n A239709

%o Answer: a(n)"

%o | a amax an b bmax k terms p q p_i q_j a_b amin bamin |

%o terms := SortedCollection new.

%o p_i := OrderedCollection new.

%o q_j := OrderedCollection new.

%o a_b := OrderedCollection new.

%o p_i add: 1.

%o q_j add: 1.

%o a_b add: 1.

%o k := 0.

%o b := 2.

%o bmax := b.

%o p := b * b.

%o q := b.

%o a := p + q - 1.

%o p_i add: p.

%o q_j add: q.

%o a_b add: a.

%o amax := 2 * (b + 1) + a.

%o an := 0.

%o [(k < self and: [a < amax]) or: [a < an]] whileTrue:

%o [[(k < self and: [a < amax]) or: [a < an]] whileTrue:

%o [[q < p and: [(k < self and: [a < amax]) or: [a < an]]] whileTrue:

%o [a isPrime2

%o ifTrue:

%o [(terms includes: a)

%o ifFalse:

%o [k := k + 1.

%o terms add: a.

%o k >= self ifTrue: [an := terms at: self]]].

%o q := b * q.

%o a := p + q - 1].

%o p = q

%o ifTrue:

%o [p := b * p.

%o q := b.

%o a := p + q - 1].

%o p_i at: b put: p.

%o q_j at: b put: q.

%o a_b at: b put: a].

%o amin := a.

%o 2 to: b - 1

%o do:

%o [:bb |

%o (a_b at: bb) < amin

%o ifTrue:

%o [amin := a_b at: bb.

%o bamin := bb]].

%o b + 1 to: bmax

%o do:

%o [:bb |

%o (a_b at: bb) < amin

%o ifTrue:

%o [amin := a_b at: bb.

%o bamin := bb]].

%o amin < (a min: amax)

%o ifTrue:

%o [b := bamin.

%o p := p_i at: b.

%o q := q_j at: b.

%o a := a_b at: b]

%o ifFalse:

%o [bmax := bmax + 1.

%o b := bmax.

%o p := b * b.

%o q := b.

%o a := p + q - 1.

%o p_i add: p.

%o q_j add: q.

%o a_b add: a.

%o amax := 2 * (b + 1) + a max: amax]].

%o ^terms copyFrom: 1 to: self

%o [by_Hieronymus Fischer_, Apr 20 2014]

%Y Cf. A239710, A239711, A239712 - A239720.

%Y Cf. A239708, A018900.

%K nonn

%O 1,1

%A _Hieronymus Fischer_, Mar 27 2014