%I #42 Jun 20 2024 08:37:55
%S 1,3,5,2,4,6,8,10,7,9,11,13,15,12,14,16,18,20,17,19,21,23,25,22,24,26,
%T 28,30,27,29,31,33,35,32,34,36,38,40,37,39,41,43,45,42,44,46,48,50,47,
%U 49,51,53,55,52,54,56,58,60,57,59,61,63,65,62,64,66,68,70,67,69,71,73
%N a(1)=1, a(2)=3, a(3)=5, a(4)=2, a(5)=4; for n > 5, a(n) = a(n-5) + 5.
%C "Greedy Dragons" permutation of the natural numbers, inverse of A065187.
%C This permutation is produced by a simple greedy algorithm: walk along each successive antidiagonal of an infinite array and place a Shoogi dragon piece (i.e., the "promoted" rook, Ryuu, that moves like a chess rook, but can also move one square diagonally) in the first available position where it is not threatened by any dragon already placed.
%C I.e., this permutation satisfies the condition that p(i+1) != p(i)+-1 for all i.
%C Alternatively, this is obtained directly if n-1 is converted to base 5, the least significant digit is doubled (modulo 5, i.e., 0->0, 1->2, 2->4, 3->1, 4->3) and one is added back to the resulting number.
%C a(1) = 1, a(n) = smallest number such that no two successive terms differ by 1 and no two terms are equal. - _Amarnath Murthy_, May 06 2003
%C This is also the lexicographic first positive sequence such that the distance between any subsequent terms, |a(n+1)-a(n)|, is a prime number and no number occurs twice, with a(1) = 1: A variant of A277618, which obeys the same rules but starts with a(0) = 0; and of A277617, which is defined similarly with squares > 1 instead of primes. - _M. F. Hasler_, Oct 23 2016
%H Harry J. Smith, <a href="/A065186/b065186.txt">Table of n, a(n) for n = 1..1000</a>
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,0,1,-1).
%F a(n) = n + ((n-1) mod 5) - 5*(floor(((n-1) mod 5)/3)).
%F G.f.: x*(x^5 + 2*x^4 - 3*x^3 + 2*x^2 + 2*x + 1)/((x - 1)*(x^5 - 1))
%F a(n) = a(n-1) + a(n-5) - a(n-6), with n>6, a(1)=1, a(2)=3, a(3)=5, a(4)=2, a(5)=4, a(6)=6. - _Harvey P. Dale_, Mar 11 2012
%p [seq(GreedyDragonsDirect(j),j=1..125)]; GreedyDragonsDirect := n -> n + ((n-1) mod 5) - 5*(floor((n-1 mod 5)/3));
%p Or empirically, by using the algorithm given at A065188: GreedyDragons := upto_n -> PM2PL(GreedyNonThreateningPermutation(upto_n,1,1),upto_n);
%t RecurrenceTable[{a[1] == 1, a[2] == 3, a[3] == 5, a[4] == 2, a[5] == 4, a[n] == a[n - 5] + 5}, a, {n, 80}] (* or *) LinearRecurrence[{1, 0, 0, 0, 1, -1}, {1, 3, 5, 2, 4, 6}, 80] (* _Harvey P. Dale_, Mar 11 2012 *)
%t Flatten[Table[5n + {1, 3, 5, 2, 4}, {n, 0, 14}]] (* _Alonso del Arte_, Jul 25 2017 *)
%o (PARI) { for (n=1, 1000, if (n>5, a=a5 + 5; a5=a4; a4=a3; a3=a2; a2=a1; a1=a, if (n==1, a=a5=1, if (n==2, a=a4=3, if (n==3, a=a3=5, if (n==4, a=a2=2, a=a1=4))))); write("b065186.txt", n, " ", a) ) } \\ _Harry J. Smith_, Oct 13 2009
%o (PARI) n=1;v=[n];while(n<200,if(isprime(abs(n-v[#v]))&&!vecsearch(vecsort(v),n),v=concat(v,n);n=1);n++);v \\ _Derek Orr_, Jul 24 2017
%o (PARI) a(n) = n--; [1,3,5,2,4][n%5+1]+5*(n\5) \\ _David A. Corneth_, Jul 24 2017
%o (PARI) first(n) = my(v = [1,3,5,2,4]); if(n < 5, return(vector(n, i, v[i])), v = concat(v, vector(n-5))); for(i=6, n, v[i]=5 + v[i-5]); v \\ _David A. Corneth_, Jul 24 2017
%o (PARI) nxt(n) = if(n%5, n+2, n-3) \\ _David A. Corneth_, Jul 24 2017
%Y "Greedy Queens" and "Quintal Queens" permutations: A065188, A065257.
%Y Cf. A065186.
%K nonn,easy
%O 1,2
%A _Antti Karttunen_, Oct 19 2001