%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