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
KEYWORD
nonn,easy
AUTHOR
Alonso del Arte, Jun 03 2020
STATUS
approved