A335365 Numbers that are unreachable by the process of starting from 1 and adding 5 and/or multiplying by 3.

2, 4, 5, 7, 10, 12, 15, 17, 20, 22, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100, 105, 110, 115, 120, 125, 130, 135, 140, 145, 150, 155, 160, 165, 170, 175, 180, 185, 190, 195, 200, 205, 210, 215, 220, 225, 230, 235, 240, 245, 250, 255, 260, 265, 270, 275, 280, 285

Offset

1,1

Comments

Start with 1. Add 5 or multiply by 3. Then either add 5 or multiply by 3, and so on and so forth. Following both branches at each step, we can create a tree like this:

1

................../ \..................

6 3

11......../ \........18 8......../ \........9

/ \ / \ / \ / \

/ \ / \ / \ / \

/ \ / \ / \ / \

16 33 23 54 13 24 14 27

21 48 38 99 28 69 59 162 18 39 29 72 19 42 32 81

According to Haverbeke (2019), some numbers, like 13, are reachable by this process in at least one way. Other numbers, like 15, are completely unreachable.

In fact, almost all positive integers that are not multiples of 5 are reachable, and all multiples of 5 (A008587) are unreachable.

The latter assertion is proven easily enough by taking note of the powers of 3 modulo 5: 1, 3, 4, 2, 1, 3, 4, 2, 1, 3, 4, 2, ... (A070352).

As for the former assertion, it is enough to note that 26, 27, 28 and 29 are reachable. Given 5k + r, with k > 4 and r one of 1, 2, 3, 4, start with the solution for 25 + r and then, k - 5 times, add 5.

More precisely the sequence consists of all multiples of 5, numbers less than 25 congruent to 2 (mod 5), and 4. - M. F. Hasler, Jun 05 2020

References

Marijn Haverbeke, Eloquent JavaScript, 3rd Ed. San Francisco (2019): No Starch, p. 51.

Links

Colin Barker, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (2,-1).

Formula

G.f.: (2*x^11 + x^10 - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 + x^3 - x^2 + 2)*x/(x - 1)^2. - Alois P. Heinz, Jun 05 2020

From Colin Barker, Jun 07 2020: (Start)

a(n) = 2*a(n-1) - a(n-2) for n>12.

a(n) = 5*(n-6) for n>10.

(End)

Example

Starting with 1, either adding 5 or multiplying by 3 results in a number greater than 2, so 2 is unreachable and therefore in the sequence.
Starting with 1, multiplying by 3 gives 3, proving 3 is reachable and therefore not in the sequence.

Mathematica

LinearRecurrence[{2, -1}, {2, 4, 5, 7, 10, 12, 15, 17, 20, 22, 25, 30}, 70] (* Harvey P. Dale, Apr 01 2023 *)

Prog

(JavaScript) // See Haverbeke (2019).
(Scala) // Based on Haverbeke (2019)
def find153Sol(n: Int): List[Int] = {
  def recur153(curr: Int, history: List[Int]): List[Int] = {
    if (curr == n) history.drop(1) :+ n else if (curr > n) List() else {
      val add5Branch = recur153(curr + 5, history :+ curr)
      if (add5Branch.nonEmpty) add5Branch
          else recur153(curr * 3, history :+ curr)
    }
  }
  recur153(1, List(1))
}
(1 to 200).filter(find153Sol(_).isEmpty)
(PARI) {is(n)=!(n%5&& !while(n>4, n%3|| is(n/3)|| break (n=1); n-=5)&& n%2==1)} \\ Using exhaustive search, for illustration. - M. F. Hasler, Jun 05 2020
(PARI) select( {is(n)=n%5==0|| (n<23&&(n%5==2||n==4))}, [1..199]) \\ Much more efficient. - M. F. Hasler, Jun 05 2020
(PARI) Vec(x*(2 - x^2 + x^3 + x^4 - x^5 + x^6 - x^7 + x^8 - x^9 + x^10 + 2*x^11) / (1 - x)^2 + O(x^50)) \\ Colin Barker, Jun 07 2020

Crossrefs

Cf. A008587 (subset), A070352, A335392.

Subsets of the complement: A000244, A016861, A016873 (except for first five terms), A016885, A016897 (except for 4).

Sequence in context: A231013 A231008 A092311 * A186386 A247589 A361070

Adjacent sequences: A335362 A335363 A335364 * A335366 A335367 A335368

Keyword

nonn,easy

Author

Alonso del Arte, Jun 03 2020

Status

approved