cp's OEIS Frontend

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

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