login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A335365 Numbers that are unreachable by the process of starting from 1 and adding 5 and/or multiplying by 3. 5
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 (list; graph; refs; listen; history; text; internal format)
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.

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 A058212

Adjacent sequences:  A335362 A335363 A335364 * A335366 A335367 A335368

KEYWORD

nonn,easy

AUTHOR

Alonso del Arte, Jun 03 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 18 18:33 EDT 2021. Contains 343998 sequences. (Running on oeis4.)