

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(n1)  a(n2) for n>12.
a(n) = 5*(n6) 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==2n==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



