|
%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
|
