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

5, 11, 17, 19, 23, 29, 41, 47, 67, 71, 79, 83, 89, 107, 109, 131, 149, 181, 191, 239, 251, 257, 263, 269, 271, 349, 379, 383, 419, 461, 599, 701, 809, 811, 929, 971, 991, 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

Offset

1,1

Comments

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)).

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.

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.

Links

Hieronymus Fischer, Table of n, a(n) for n = 1..10000

Example

a(1) = 5, since 5 = 2^2 + 2^1 - 1 is prime.
a(2) = 11, since 11 = 2^3 + 2^2 - 1 is prime.
a(6) = 29, since 29 = 3^3 + 3^1 - 1 is prime.
a(10^1) = 71.
a(10^2) = 13109.
a(10^3) = 9336079.
a(10^4) = 2569932329.
a(10^5) = 455578426189.
a(10^6) = 68543190483641.

Prog

(Smalltalk)
A239709
"Answers the n-th term of A239709.
  Iterative calculation using A239709_termsLTn.
  Usage: n A239709
  Answer: a(n)"
  | n terms m |
  terms := SortedCollection new.
  n := self.
  m := (n prime // 2) squared.
  terms := m A239709_termsLTn.
  [terms size < n] whileTrue:
         [m := 2 * m.
         terms := m A239709_termsLTn].
  ^terms at: n
  "Remark: A last line of
  ^terms copyFrom: 1 to: n
  answers an array of the first n terms"
[by_Hieronymus Fischer_, Apr 14 2014]
-----------
(Smalltalk)
A239709_termsLTn
  "Answers all the terms of A239709 which are < n.
  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.
  Usage: n A239709_termsLTn
  Answer: #(5 11 17 19 23 ...) [terms < n]"
  | bmax p q n m terms a |
  terms := OrderedCollection new.
  n := self.
  bmax := n sqrtTruncated.
  2 to: bmax
     do:
         [:b |
         m := 1 + (n floorLog: b).
         p := b.
         2 to: m
              by: 1
              do:
                   [:i |
                   p := b * p.
                   q := b.
                   1 to: i - 1
                        by: 1
                        do:
                            [:j |
                            a := p + q - 1.
                            a < n ifTrue: [a isPrime ifTrue: [terms add: a]].
                            q := b * q]]].
  ^terms asSet asArray sorted
[by_Hieronymus Fischer_, Apr 14 2014]
-----------
(Smalltalk)
A239709nTerms
  "Alternative version: Answers the first n terms of A239709. Direct calculation by scanning the numbers b^i + b^j - 1 in increasing order.
  Usage: n A239709
  Answer: a(n)"
  | a amax an b bmax k terms p q p_i q_j a_b amin bamin |
  terms := SortedCollection new.
  p_i := OrderedCollection new.
  q_j := OrderedCollection new.
  a_b := OrderedCollection new.
  p_i add: 1.
  q_j add: 1.
  a_b add: 1.
  k := 0.
  b := 2.
  bmax := b.
  p := b * b.
  q := b.
  a := p + q - 1.
  p_i add: p.
  q_j add: q.
  a_b add: a.
  amax := 2 * (b + 1) + a.
  an := 0.
  [(k < self and: [a < amax]) or: [a < an]] whileTrue:
         [[(k < self and: [a < amax]) or: [a < an]] whileTrue:
                   [[q < p and: [(k < self and: [a < amax]) or: [a < an]]] whileTrue:
                            [a isPrime2
                                 ifTrue:
                                      [(terms includes: a)
                                          ifFalse:
                                               [k := k + 1.
                                               terms add: a.
                                               k >= self ifTrue: [an := terms at: self]]].
                            q := b * q.
                            a := p + q - 1].
                   p = q
                        ifTrue:
                            [p := b * p.
                            q := b.
                            a := p + q - 1].
                   p_i at: b put: p.
                   q_j at: b put: q.
                   a_b at: b put: a].
         amin := a.
         2 to: b - 1
              do:
                   [:bb |
                   (a_b at: bb) < amin
                        ifTrue:
                            [amin := a_b at: bb.
                            bamin := bb]].
         b + 1 to: bmax
              do:
                   [:bb |
                   (a_b at: bb) < amin
                        ifTrue:
                            [amin := a_b at: bb.
                            bamin := bb]].
         amin < (a min: amax)
              ifTrue:
                   [b := bamin.
                   p := p_i at: b.
                   q := q_j at: b.
                   a := a_b at: b]
              ifFalse:
                   [bmax := bmax + 1.
                   b := bmax.
                   p := b * b.
                   q := b.
                   a := p + q - 1.
                   p_i add: p.
                   q_j add: q.
                   a_b add: a.
                   amax := 2 * (b + 1) + a max: amax]].
  ^terms copyFrom: 1 to: self
[by_Hieronymus Fischer_, Apr 20 2014]

Crossrefs

Cf. A239710, A239711, A239712 - A239720.

Cf. A239708, A018900.

Sequence in context: A317048 A081717 A096264 * A175249 A271982 A338239

Adjacent sequences: A239706 A239707 A239708 * A239710 A239711 A239712

Keyword

nonn

Author

Hieronymus Fischer, Mar 27 2014

Status

approved