A277617 -id:A277617 - cp's OEIS frontend

A377091 a(0) = 0; thereafter a(n) is the least integer (in absolute value) not yet in the sequence such that the absolute difference between a(n-1) and a(n) is a square; in case of a tie, preference is given to the positive value.

0, 1, 2, -2, -1, 3, 4, 5, -4, -3, 6, 7, 8, -8, -7, -6, -5, -9, -10, -11, -12, 13, 9, 10, 11, 12, -13, -14, -15, -16, -17, -18, 18, 14, 15, 16, 17, -19, -20, -21, -22, -23, -24, 25, 21, 20, 19, 23, 22, 26, 27, 28, 24, -25, -26, -27, -28, -29, -30, -31, -32, 32

Offset: 0

Rémy Sigrist, Oct 16 2024

Conjecture 1: Every integer (positive or negative) appears in this sequence.
Conjecture 2: For n > 16, |a(n)| is within sqrt(n/2) of floor(n/2). See A379071. - N. J. A. Sloane, Dec 29 2024 [Corrected by Paolo Xausa, Jan 21 2025]
Conjecture 3: lim sup ||a(n)| - floor(n/2)|/sqrt(n) = 1/2. (See link.) - N. J. A. Sloane and Paolo Xausa, Feb 03 2025
Conjecture 4: After a(n) has been found, the sequence contains all numbers in the range [0,f(n)], where lim sup f(n) = (n-sqrt(n))/2. There is a corresponding conjecture for the negative terms. See A379067. - N. J. A. Sloane and Paolo Xausa, Feb 13 2025

			The initial terms are:
  n   a(n)  |a(n)-a(n-1)|
  --  ----  -------------
   0     0  N/A
   1     1  1^2
   2     2  1^2
   3    -2  2^2
   4    -1  1^2
   5     3  2^2
   6     4  1^2
   7     5  1^2
   8    -4  3^2
   9    -3  1^2
  10     6  3^2
  11     7  1^2
  12     8  1^2
  13    -8  4^2
  14    -7  1^2

N. J. A. Sloane, Table of n, a(n) for n = 0..20000 [First 10000 terms from Rémy Sigrist]
M. F. Hasler, Interactive spiral graph representation of the first n terms, Jan 18 2025.
Kerry Mitchell, Spiral graph representation of first 31 terms
Kerry Mitchell, Colored spiral graph representation of first 100 terms
Chris Scussel, Spiral graph representation of 5000 terms
Rémy Sigrist, Scatterplot of the first 10000 terms of the partial sums
Rémy Sigrist, Christmas card based on graph of the partial sums [Rotate graph by 90 degs, add color and decorations]
Rémy Sigrist, PARI program
N. J. A. Sloane, Table of n, a(n) for n = 0..250000
N. J. A. Sloane, Spiral graph representation of first 28 terms [Hand-drawn]
Paolo Xausa, Scatterplot of ||a(n)| - floor(n/2)| for 0 <= n <= 200000. The orange line is sqrt(n)/2.

This sequence is a variant of A277616 allowing negative values.
Cf. A277617, A277618, A377090, A377092.
A large number of sequences have been derived from the present sequence in the hope (so far unfulfilled) of finding a formula or recurrence: see A379057-A379078, A379786-A379798, A379802, A379803, A379804, A379880, A380223, A380224, A380225, A382715-A382718.
First differences are A379061 (certainly the most relevant derived sequence). - M. F. Hasler, Feb 08 2025
"Lexicographically earliest" sequences for which there is a proof that every number that could appear does appear: A064413, A098550, A109812, A121216, A347113, etc. - N. J. A. Sloane, Feb 08 2025

A377091 = [0]; A377091.least_unused = 1;
function a(n){
  for(let i = A377091.length-1; i < n; ++i) {
    let k = A377091.least_unused;
    while(!Number.isInteger(Math.sqrt(Math.abs(A377091[i] - k)))
          || A377091.indexOf(k) > 0) k = (k<0)-k;
    A377091.push(k);
    if (k == A377091.least_unused) {
      do k = (k<0)-k; while ( A377091.indexOf( k ) > 0 );
      A377091.least_unused = k;
  } };
  return A377091[n];
} // M. F. Hasler, Jan 26 2025

h := proc(b, a, i) option remember; ifelse(issqr(abs(a[-1] - i)) and not is(i in a), ifelse(b < nops(a) + 1, a, h(b, [op(a), i], 1)), h(b, a, ifelse(i < 0, 1 - i, -i))) end:
a_list := length -> h(length, [0], 1): a_list(62);  # Peter Luschny, Jan 20 2025

A377091list[nmax_] := Module[{s, a, u = 1}, s[_] := False; s[0] = True; NestList[(While[s[u] && s[-u], u++]; a = u; While[s[a] || !IntegerQ[Sqrt[Abs[# - a]]], a = Boole[a < 0] - a]; s[a] = True; a) &, 0,nmax]];
A377091list[100] (* Paolo Xausa, Mar 18 2025 *)

PARI
```
\\ See Links section.
```

A377091_upto(n,S=[])={vector(n+1, k, S=setunion(S, [n=if(k>1, k=1; while(setsearch(S,k) || !issquare(abs(n-k)), k=(k<0)-k); k)]); n)} \\ M. F. Hasler, Jan 18 2025

from math import isqrt
from itertools import count, islice
def cond(n): return isqrt(n)**2 == n
def agen(): # generator of terms
    an, aset, m = 0, {0}, 1
    for n in count(0):
        yield an
        an = next(s for k in count(m) for s in [k, -k] if s not in aset and cond(abs(an-s)))
        aset.add(an)
        while m in aset and -m in aset: m += 1
print(list(islice(agen(), 62))) # Michael S. Branicky, Dec 25 2024

from math import sqrt
def a_list(b: int, a: list[int] = [0], i: int = 1) -> list[int]:
    if sqrt(abs(a[-1] - i)).is_integer() and not (i in a):
        a += [i]
        if b < len(a):
            return a
        else:
            return a_list(b, a)
    else:
        return a_list(b, a, int(i < 0) - i)
print(a_list(40))  # Peter Luschny, Jan 20 2025

class A377091: # A377091(n) gives a(n)
    terms = [0]; N = 1 # next candidate
    def _new_(A, n): A.extend(A, n-len(A.terms)+1); return A.terms[n]
    def extend(A, n): any((k:=A.N) in A.terms and setattr(A, 'N', k:=(k<0)-k) or
        A.terms.append(next(k for _ in range(9**9) if (abs(A.terms[-1]-k)**.5)
       .is_integer() and k not in A.terms or not(k:=(k<0)-k))) for _ in range(n))
# M. F. Hasler, Feb 08 2025

A065186 a(1)=1, a(2)=3, a(3)=5, a(4)=2, a(5)=4; for n > 5, a(n) = a(n-5) + 5.

Original entry on oeis.org

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, 28, 30, 27, 29, 31, 33, 35, 32, 34, 36, 38, 40, 37, 39, 41, 43, 45, 42, 44, 46, 48, 50, 47, 49, 51, 53, 55, 52, 54, 56, 58, 60, 57, 59, 61, 63, 65, 62, 64, 66, 68, 70, 67, 69, 71, 73

Offset: 1

Antti Karttunen, Oct 19 2001

"Greedy Dragons" permutation of the natural numbers, inverse of A065187.
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.
I.e., this permutation satisfies the condition that p(i+1) != p(i)+-1 for all i.
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.
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
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

Harry J. Smith, Table of n, a(n) for n = 1..1000
Index entries for sequences that are permutations of the natural numbers
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,1,-1).

"Greedy Queens" and "Quintal Queens" permutations: A065188, A065257.

Cf. A065186.

[seq(GreedyDragonsDirect(j),j=1..125)]; GreedyDragonsDirect := n -> n + ((n-1) mod 5) - 5*(floor((n-1 mod 5)/3));
Or empirically, by using the algorithm given at A065188: GreedyDragons := upto_n -> PM2PL(GreedyNonThreateningPermutation(upto_n,1,1),upto_n);

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 *)
Flatten[Table[5n + {1, 3, 5, 2, 4}, {n, 0, 14}]] (* Alonso del Arte, Jul 25 2017 *)

{ 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

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

a(n) = n--; [1,3,5,2,4][n%5+1]+5*(n\5) \\ David A. Corneth, Jul 24 2017

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

nxt(n) = if(n%5, n+2, n-3) \\ David A. Corneth, Jul 24 2017

a(n) = n + ((n-1) mod 5) - 5*(floor(((n-1) mod 5)/3)).
G.f.: x*(x^5 + 2*x^4 - 3*x^3 + 2*x^2 + 2*x + 1)/((x - 1)*(x^5 - 1))
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

A277616 Lexicographically earliest sequence such that |a(n+1)-a(n)| is a square > 1 (for all n) and no number occurs twice; a(0) = 0.

Original entry on oeis.org

0, 4, 8, 12, 3, 7, 11, 2, 6, 10, 1, 5, 9, 13, 17, 21, 25, 16, 20, 24, 15, 19, 23, 14, 18, 22, 26, 30, 34, 38, 29, 33, 37, 28, 32, 36, 27, 31, 35, 39, 43, 47, 51, 42, 46, 50, 41, 45, 49, 40, 44, 48, 52, 56, 60, 64, 55, 59, 63, 54, 58, 62, 53, 57, 61, 65, 69, 73, 77, 68, 72, 76, 67, 71, 75, 66, 70, 74, 78, 82, 86, 90, 81, 85, 89, 80, 84, 88, 79, 83, 87

Offset: 0

Eric Angelini, Oct 23 2016

A variant is given by A277617, defined in the same way but starting with a(1) = 1. Another variant is A277618, which is defined in a similar way, but with primes instead of squares.
Yet another version is A377091, with an interesting graph. - N. J. A. Sloane, Dec 25 2024
It turns out that the steps a(n+1)-a(n) are either +4 or -9, no other squares occur as distances between successive terms. Indeed, one finds a(13) = 13 and all numbers from 0 to 12 occur as a(n) for 0 <= n <= 12. So there are no "holes", which entails the periodicity. More precisely, a({0, ..., 13k-1}) = {0, ..., 13k-1} and a(13k) = 13k for all k. This also implies that the sequence is a permutation of the nonnegative integers. - M. F. Hasler, Oct 24 2016

			The possible (absolute) differences between subsequent terms are the squares larger than one, i.e., { 4, 9, 16, ... }.
After 0, the smallest possibility is 0 + 2^2 = 4, the next one is 4 + 2^2 = 8, and then 8 + 2^2 = 12. Now the next term is 12 - 3^2 = 3, thereafter 3 + 2^2 = 7, etc.
In a similar way, 11 is followed by 11 - 3^2, and 10 is followed by 10 - 3^2 = 1.
Thereafter, the next step of -9 will be after 25.
The sequence of steps (first differences) consists of repetitions of the 13 terms (4, 4, 4, -9, 4, 4, -9, 4, 4, -9, 4, 4, 4) which sum to 13.

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,0,0,0,0,0,0,1,-1).

Cf. A034175, A277617, A277618, A377091.

A277616 := proc(n) local L,i,t1; option remember;
L := [0, 4, 8, 12, 3, 7, 11, 2, 6, 10, 1, 5, 9, 13];
if n <= 13 then return(L[n+1]) else A277616(n-13)+13; fi; end; # N. J. A. Sloane, Jan 12 2025

LinearRecurrence[{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1}, {0, 4, 8, 12, 3, 7, 11, 2, 6, 10, 1, 5, 9, 13}, 100] (* Paolo Xausa, Jan 16 2025 *)

{u=[a=0];(chk(n)=(!#u||(n>u[1]&&!setsearch(u,n)))&&(u=setunion(u,[n]))&&!while(#u>1&&u[2]==u[1]+1,u=u[^1]));for(n=1,99,print1(a",");for(k=-sqrtint(a+!a-1),9e9,k^2>1||next;chk(a+k*abs(k))||next;a+=k*abs(k);break))} \\ M. F. Hasler, Oct 23 2016

A277616(n,i=[0,4,8,12,3,7,11,2,6,10,1,5,9])=i[n%#i+1]+n\#i*#i \\ M. F. Hasler, Oct 24 2016

a(n+13) = a(n)+13 for all n.
From Chai Wah Wu, Mar 30 2023: (Start)
a(n) = a(n-1) + a(n-13) - a(n-14) for n > 13.
G.f.: x*(4*x^12 + 4*x^11 + 4*x^10 - 9*x^9 + 4*x^8 + 4*x^7 - 9*x^6 + 4*x^5 + 4*x^4 - 9*x^3 + 4*x^2 + 4*x + 4)/(x^14 - x^13 - x + 1). (End)

A277618 Lexicographically earliest nonnegative sequence such that |a(n+1)-a(n)| is a prime number, and no number occurs twice; a(0) = 0.

Original entry on oeis.org

0, 2, 4, 1, 3, 5, 7, 9, 6, 8, 10, 12, 14, 11, 13, 15, 17, 19, 16, 18, 20, 22, 24, 21, 23, 25, 27, 29, 26, 28, 30, 32, 34, 31, 33, 35, 37, 39, 36, 38, 40, 42, 44, 41, 43, 45, 47, 49, 46, 48, 50, 52, 54, 51, 53, 55, 57, 59, 56, 58, 60, 62, 64, 61, 63, 65, 67, 69, 66, 68, 70, 72, 74, 71, 73, 75, 77, 79, 76, 78, 80, 82, 84, 81, 83, 85, 87, 89, 86, 88, 90

Offset: 0

Eric Angelini and M. F. Hasler, Oct 23 2016

A variant of A277616, which is defined in a similar way with squares > 1 instead of primes.

The steps a(n+1)-a(n) are either +2 or -3, after 10 terms we get a(n+10), and the first 10 terms are all numbers between 0 and 9: This sequence is obviously a permutation of the nonnegative integers, with a(n) = a(n-5) + 5 for all n > 5. The strictly positive variant (starting with a(1) = 1) is given by A065186.

Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,1,-1).

Cf. A277616, A277617, A065186.

Table[n - 2 + Mod[n - 3, 5], {n, 0, 500}] (* Fred Patrick Doty, Aug 03 2020 *)

{u=[a=0];(chk(n)=(!#u||(n>u[1]&&!setsearch(u,n)))&&(u=setunion(u,[n]))&&!while(#u>1&&u[2]==u[1]+1,u=u[^1]));for(n=1,99,print1(a","); for(k=-primepi(a+!a-1),9e9, k||next; chk(a+sign(k)*prime(abs(k)))||next; a+=sign(k)*prime(abs(k));break))}

A277618(n,i=[0,2,4,1,3])=i[n%#i+1]+n\#i*#i

a(n) = a(n-5) + 5 for all n > 5.
a(n) = A065186(n+1) - 1.
G.f.: x*(2*x^4 + 2*x^3 - 3*x^2 + 2*x + 2)/(x^6 - x^5 - x + 1). - Chai Wah Wu, Mar 30 2023

Offset corrected by R. J. Mathar, Jun 19 2021

cp's OEIS Frontend

A377091 a(0) = 0; thereafter a(n) is the least integer (in absolute value) not yet in the sequence such that the absolute difference between a(n-1) and a(n) is a square; in case of a tie, preference is given to the positive value.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

JavaScript

Maple

Mathematica

PARI

PARI

Python

Python

Python

A065186 a(1)=1, a(2)=3, a(3)=5, a(4)=2, a(5)=4; for n > 5, a(n) = a(n-5) + 5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

Formula

A277616 Lexicographically earliest sequence such that |a(n+1)-a(n)| is a square > 1 (for all n) and no number occurs twice; a(0) = 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A277618 Lexicographically earliest nonnegative sequence such that |a(n+1)-a(n)| is a prime number, and no number occurs twice; a(0) = 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions