Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #34 Apr 01 2023 11:24:00
%S 2,4,5,7,10,12,15,17,20,22,25,30,35,40,45,50,55,60,65,70,75,80,85,90,
%T 95,100,105,110,115,120,125,130,135,140,145,150,155,160,165,170,175,
%U 180,185,190,195,200,205,210,215,220,225,230,235,240,245,250,255,260,265,270,275,280,285
%N Numbers that are unreachable by the process of starting from 1 and adding 5 and/or multiplying by 3.
%C 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:
%C 1
%C ................../ \..................
%C 6 3
%C 11......../ \........18 8......../ \........9
%C / \ / \ / \ / \
%C / \ / \ / \ / \
%C / \ / \ / \ / \
%C 16 33 23 54 13 24 14 27
%C 21 48 38 99 28 69 59 162 18 39 29 72 19 42 32 81
%C 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.
%C In fact, almost all positive integers that are not multiples of 5 are reachable, and all multiples of 5 (A008587) are unreachable.
%C 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).
%C 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.
%C 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
%D Marijn Haverbeke, Eloquent JavaScript, 3rd Ed. San Francisco (2019): No Starch, p. 51.
%H Colin Barker, <a href="/A335365/b335365.txt">Table of n, a(n) for n = 1..1000</a>
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1).
%F 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
%F From _Colin Barker_, Jun 07 2020: (Start)
%F a(n) = 2*a(n-1) - a(n-2) for n>12.
%F a(n) = 5*(n-6) for n>10.
%F (End)
%e 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.
%e Starting with 1, multiplying by 3 gives 3, proving 3 is reachable and therefore not in the sequence.
%t LinearRecurrence[{2,-1},{2,4,5,7,10,12,15,17,20,22,25,30},70] (* _Harvey P. Dale_, Apr 01 2023 *)
%o (JavaScript) // See Haverbeke (2019).
%o (Scala) // Based on Haverbeke (2019)
%o def find153Sol(n: Int): List[Int] = {
%o def recur153(curr: Int, history: List[Int]): List[Int] = {
%o if (curr == n) history.drop(1) :+ n else if (curr > n) List() else {
%o val add5Branch = recur153(curr + 5, history :+ curr)
%o if (add5Branch.nonEmpty) add5Branch
%o else recur153(curr * 3, history :+ curr)
%o }
%o }
%o recur153(1, List(1))
%o }
%o (1 to 200).filter(find153Sol(_).isEmpty)
%o (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
%o (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
%o (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
%Y Cf. A008587 (subset), A070352, A335392.
%Y Subsets of the complement: A000244, A016861, A016873 (except for first five terms), A016885, A016897 (except for 4).
%K nonn,easy
%O 1,1
%A _Alonso del Arte_, Jun 03 2020