A335392 -id:A335392 - cp's OEIS frontend

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

Alonso del Arte, Jun 03 2020

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

			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.

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

Colin Barker, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (2,-1).

Cf. A008587 (subset), A070352, A335392.

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

JavaScript
```
// See Haverbeke (2019).
```

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

{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

select( {is(n)=n%5==0|| (n<23&&(n%5==2||n==4))}, [1..199]) \\ Much more efficient. - M. F. Hasler, Jun 05 2020

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

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

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)

A335393 a(1) = 1 and for any n >= 1, a(2n) = a(n) + 5, a(2n+1) = a(n) * 3.

Original entry on oeis.org

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, 26, 63, 53, 144, 43, 114, 104, 297, 33, 84, 74, 207, 64, 177, 167, 486, 23, 54, 44, 117, 34, 87, 77, 216, 24, 57, 47, 126, 37, 96, 86, 243

Offset: 1

Rémy Sigrist, Jun 05 2020

nonn

All terms belong to A335155.

For any k > 0, the value k appears A335392(k) times.

			a(12) = a(6) + 5 = a(3) + 5 + 5 = a(1) * 3 + 5 + 5 = 1 * 3 + 5 + 5 = 13.

Rémy Sigrist, Table of n, a(n) for n = 1..8192

Cf. A335155, A335365, A335392.

a(n) = { if (n==1, 1, n%2==0, a(n\2)+5, a(n\2)*3) }

a(2^k) = 1 + 5*k for any k >= 0.

a(2^k-1) = 2^(k-1) for any k > 0.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

JavaScript

Mathematica

PARI

PARI

PARI

Scala

Formula

A335393 a(1) = 1 and for any n >= 1, a(2n) = a(n) + 5, a(2n+1) = a(n) * 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

JavaScript

Mathematica

PARI

PARI

PARI

Scala

Formula

A335393 a(1) = 1 and for any n >= 1, a(2*n) = a(n) + 5, a(2*n+1) = a(n) * 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A335393 a(1) = 1 and for any n >= 1, a(2n) = a(n) + 5, a(2n+1) = a(n) * 3.