Slater-Velez permutation

Question

Let's build a sequence of positive integers. The rule will be that the next number will be the smallest number which:

It hasn't already appeared in the sequence
Its absolute difference from the number preceding it wouldn't be equal to any previous absolute difference between consecutive elements.

Task

Your task is to implement this sequence. You may use sequence defaults, found in the tag wiki.

This is code-golf so answers will be scored in bytes with fewer bytes being better.

Example

As an example let's construct the first couple of terms. The first term is 1 since it's the smallest positive integer. After that comes 2.

Sequence: 1, 2
Diffs:     1

3 is the next smallest number, but it's difference from 2 is the same as the difference between 1 and 2, so 4 is the next term.

Sequence: 1, 2, 4
Diffs:     1, 2

Now 3 still can't be added because it's difference from 4 is 1, 5 and 6 also can't be added because their diffs are 1 and 2. So the smallest number is 7.

Sequence: 1, 2, 4, 7
Diffs:     1, 2, 3

Now 3 can be added, since it's difference from 7 is 4 which we haven't seen before.

Sequence: 1, 2, 4, 7, 3
Diffs:     1, 2, 3, 4

Since the diffs count up to 4 we know the next one is at least 5, so the next number is at least 8. 8 hasn't appeared so we can add it.

Sequence: 1, 2, 4, 7, 3, 8
Diffs:     1, 2, 3, 4, 5

Test cases

This sequence is OEIS A081145. Here are the first few terms taken from OEIS:

1, 2, 4, 7, 3, 8, 14, 5, 12, 20, 6, 16, 27, 9, 21, 34, 10, 25, 41, 11, 28, 47, 13, 33, 54, 15, 37, 60, 17, 42, 68, 18, 45, 73, 19, 48, 79, 22, 55, 23, 58, 94, 24, 61, 99, 26, 66, 107, 29, 71, 115, 30, 75, 121, 31, 78, 126, 32, 81, 132, 35, 87, 140, 36, 91, 147, 38, 96, 155, 39

pxeger · Accepted Answer · 2022-01-11 12:56:38Z

8

Python, 70 bytes

a={0,p:=1}
while[print(d:=p)]:
 while(s:={p-d,-d*d})&a:d-=1
 a|=s;p-=d

Attempt This Online!

-1 each thanks to @xnor and @ovs.

Prints the sequence infinitely. Avoids the need for two storage lists by using the negative absolute difference.

edited Jan 11, 2022 at 12:56

answered Jan 11, 2022 at 11:32

pxeger

22.9k4 gold badges49 silver badges133 bronze badges

1

\$\begingroup\$ Nice idea with the negatives! Here's 71 bytes. Might be possible to shorten the initialization. \$\endgroup\$
– xnor
Jan 11, 2022 at 11:51
\$\begingroup\$ Brownie points for golfing my modified print implementation! \$\endgroup\$
– pxeger
Jan 11, 2022 at 11:58
2

\$\begingroup\$ -abs(p-n) would work as well, because a difference of 0 never happens, which means -(p-n)**2 works, which saves a byte if we keep track of w=p-n instead of n: ato.pxeger.com/… \$\endgroup\$
– ovs
Jan 11, 2022 at 12:53

Add a comment |

Fatalize · Accepted Answer · 2022-01-11 12:43:18Z

Brachylog, 16 bytes

~l.ℕ₁ᵐ≠s₂ᵇ-ᵐȧᵐ≠∧

Try it online!

Returns a list of the n first elements of the sequence.

Explanation

We basically describe the properties of the sequence: a list of positive integers, that are all different, and where each 2-element substring difference is unique.

~l.                Output is a list of length <Input>
  .ℕ₁ᵐ             Output contains strictly positive integers
  .   ≠            All elements in the output are different
  .    s₂ᵇ         Find all sublists of 2 consecutive elements in the Output
          -ᵐ       Map subtraction
            ȧᵐ     Map absolute value
              ≠    All results must be different
               ∧   Implicit labelling of elements in the output to match these constraints

Kevin Cruijssen · Accepted Answer · 2022-01-11 15:07:32Z

5

05AB1E, 15 11 bytes

λλû¥+λ«∞sKн

-4 bytes thanks to @ovs.

Outputs the infinite sequence.

Try it online.

Explanation:

λ           # Start a recursive environment
            # to output the infinite sequence
            # Implicitly starting with a(0)=1
            # Where every following a(n) is calculated as follows:
            #  (implicitly push a(n-1))
 λ          #  Push a list of all previous terms: [a(0),a(1),...,a(n-1)]
  û         #  Palindromize this list: [a(0),a(1),...,a(n-1),...,a(1),a(0)]
   ¥        #  Pop and push its forward differences
    +       #  Add the implicit a(n-1) to each
     λ«     #  Merge the list of previous terms to this list
       ∞    #  Push an infinite positive list: [1,2,3,...]
        s   #  Swap so our earlier created list is at the top again
         K  #  Remove all those values from the infinite positive list
          н #  Pop and leave just the first value
            # (after which the infinite list is output implicitly as result)

edited Jan 11, 2022 at 15:07

answered Jan 11, 2022 at 13:09

Kevin Cruijssen

118k10 gold badges134 silver badges361 bronze badges

1

\$\begingroup\$ I think λλû¥+λ«∞sKн works for 11. (λû¥ is shorter than λ¥D(«) \$\endgroup\$
– ovs
Jan 11, 2022 at 13:51
\$\begingroup\$ @ovs Thanks for the -4. I should have known just removing them from the infinite list and getting the first remaining would be shorter after I had to introduce those variables for the inner find_first-loop. But apart from that: since when is ü¥ being ¥D(« a thing?! :S \$\endgroup\$
– Kevin Cruijssen
Jan 11, 2022 at 14:52
1

\$\begingroup\$ That is û not ü ;). There is no special meaning for this, but the negative forward difference are the forward differences of the reverse (as long as you don't care about the order), and û appends the reverse to the list. \$\endgroup\$
– ovs
Jan 11, 2022 at 14:57
\$\begingroup\$ @ovs Ah lol.. I misread. Yeah ok, û is the palindrome builtin. Ok, now it makes a lot more sense than when I read ü, haha. I was so confused for a moment! xD \$\endgroup\$
– Kevin Cruijssen
Jan 11, 2022 at 15:06

Add a comment |

coltim · Accepted Answer · 2022-01-11 20:49:58Z

K (ngn/k), 43 bytes

{x,{y+(1<#?:\#'!'1_-':x,y)|/x=y}[x]/1}/[;1]

Try it online!

Takes the number of terms to generate (0-indexed, so passing 0 generates the sequence up to position 0, 4 generates the sequence up to position 4, etc etc.)

{...}/[;1] set up a do-reduce, run for the inputted number of times, seeded with 1 (the first term of the sequence)
- {...{...}[x]/1} set up a converge-reduce, fixing x (the sequence generated so far) and seeded with 1
  - (1<#?:\#'!'1_-':x,y) determine if the current value has a different absolute difference than the rest of the terms in the sequence so far
    - x,y append the value being tested to the sequence so far
    - 1_-': take the differences between successive items
    - #'!' take the absolute value of these differences
    - 1<#?:\ determine if the differences are all distinct (i.e. none are repeated)
  - (...)|/x=y set up a max-reduce (i.e. any), seeded with the check described above and run over the sequence compared to the value being tested (for equality)
  - y+ add this result to the current value being tested; if the value meets both checks, it will be unchanged and end the converge-reduce
- {x,...} append the next term in the sequence and feed it to the next iteration of the do-reduce

AZTECCO · Accepted Answer · 2022-01-12 03:02:49Z

4

Haskell, 97 bytes

(#)=notElem
g=(iterate(\l->l++[[x|x<-[1..],x#l,abs(x-last l)#zipWith((abs.).(-))l(1:l)]!!0])[]!!)

Try it online!

returns first n elements.

answered Jan 12, 2022 at 3:02

AZTECCO

10.5k1 gold badge13 silver badges58 bronze badges

Add a comment |

Madison Silver · Accepted Answer · 2022-01-12 03:50:28Z

4

Haskell, 107 bytes

e l=[last l+x*v|v<-zipWith((abs.).(-))l$1:l,x<-[-1,1]]++l
f n=head$filter(flip notElem$e$f<$>[0..n-1])[1..]

Try it Online!

-3 bytes thanks to AZTECCO

edited Jan 12, 2022 at 3:50

answered Jan 12, 2022 at 1:48

Madison Silver

6693 silver badges5 bronze badges

1

\$\begingroup\$ Nice answer, (I posted mine anyway because its different) , you can steal from mine (1:l) instead of $tail l , that's all the help I can give, but I feel like that's still something.. \$\endgroup\$
– AZTECCO
Jan 12, 2022 at 3:30

Add a comment |

lyxal · Accepted Answer · 2022-01-11 12:30:31Z

Vyxal, 20 bytes

(λ¾₌‡¯ȧtnεc¾nc∨¬;ṅ…⅛

Try it Online!

I'm probably going to take the L to better algorithms, but that's okay with me. Prints the first n numbers.

Explained

(λ¾₌‡¯ȧtnεc¾nc∨¬;ṅ…⅛
(                     # input times:
 λ..............;ṅ    #   find the first number N where:
   ₌                  #     the 
  ¾ ‡¯ȧ               #     absolute values of the deltas of the global array
          c           #     contains
  ¾    tnε            #     the absolute difference of the last item of the global array and N
              ∨¬      #     nor
           ¾nc        #     does the global array contain N
                  …⅛  #   print N and add to the global array

Kjetil S · Accepted Answer · 2022-01-11 15:51:12Z

3

Perl 5 List::Util, 64 bytes

$l=@a=0..1e3;$a[$l]=0,say$l while$l=first{$_&&!$d{abs$_-$l}++}@a

Try it online!

answered Jan 11, 2022 at 15:51

Kjetil S

5,1179 silver badges17 bronze badges

Add a comment |

pajonk · Accepted Answer · 2022-01-11 20:07:25Z

3

R, 76 bytes

while(k<-1){p=print(+T[1])
while((p-k)^2%in%diff(T)^2|k%in%T)k=k+1
T=c(k,T)}

Try it online!

Prints the sequence infinitely.

answered Jan 11, 2022 at 20:07

pajonk

14k3 gold badges18 silver badges63 bronze badges

Add a comment |

ovs · Accepted Answer · 2022-01-11 23:48:44Z

APL (Dyalog Unicode), 32 bytes

Prints the sequence without end.

{∇⍵,⍨⊃k~⍨⍳+/k←⍵,(⎕←⊃⍵)+2-/⍵,⌽⍵}1

Try it online!

{∇⍵,⍨⊃k~⍨⍳+/k←⍵,(⎕←⊃⍵)+2-/⍵,⌽⍵}1 ⍝ full program that prints the sequence indefinitely
{                             }  ⍝ recursive function taking the previous numbers as right argument ⍵
                       2-/⍵,⌽⍵   ⍝ forward and backward differences of consecutive numbers in ⍵
                 ⎕←⊃⍵            ⍝ print (and return) the previous value
                      +          ⍝ add this to all the differences
                                 ⍝ all these results are not allowed because of the absolute difference rule
              ⍵,                 ⍝ prepend the previous sequence values
            k←                   ⍝ store this list in k
          +/                     ⍝ take the sum of k (this is always larger than the maximum value)
      k~⍨⍳                       ⍝ [1 .. sum(k)] without the values in k
     ⊃                           ⍝ take the first (lowest) value
  ⍵,⍨                            ⍝ prepend to the sequence values
 ∇                               ⍝ recursive function call with updated list
                               1 ⍝ call above function with value 1

Dominic van Essen · Accepted Answer · 2022-01-12 09:24:27Z

3

R, 74 71 70 bytes

repeat T=c((u=1:(T*5))[!u%in%T&!(u-print(+T[1]))^2%in%diff(T)^2][1],T)

Try it online!

Outputs the sequence indefinitely.

Note (from OEIS A081145) that "The points appear to lie on three straight lines of slopes roughly 0.56, 1.40, 2.24 (click "graph")".
If true, then a(n) should always be less than or equal to a(n-1) multiplied by about 2.24/0.56, or 4. So here we only search in the range from 1 up to a(n-1) times 5 (to be on the safe side).

edited Jan 12, 2022 at 9:24

answered Jan 11, 2022 at 23:26

Dominic van Essen

31k2 gold badges16 silver badges51 bronze badges

Add a comment |

Arnauld · Accepted Answer · 2022-01-12 12:12:42Z

3

JavaScript (V8), 84 bytes

A full program printing the sequence forever.

for(a=[];i=1;print(p=i),a.push(i))while(a.some(q=v=>v==i|(i-p)**2==(q-(q=v))**2))i++

Try it online!

JavaScript (V8), 66 65 bytes

Using pxeger's nice idea.

for(s=p={};i=1;print(s[q]=s[i]=p=i))while(s[q=i-p,q*=-q]|s[i])i++

Try it online!

edited Jan 12, 2022 at 12:12

answered Jan 11, 2022 at 11:36

Arnauld

182k18 gold badges168 silver badges612 bronze badges

Add a comment |

Wheat Wizard · Accepted Answer · 2022-01-12 14:03:12Z

3

Haskell, 81 77 bytes

4 bytes saved by xnor

(?)=notElem
q@(a:b)!x=a:[(z:q)!(d:x)|z<-[1..],d<-[abs$a-z],z?q,d?x]!!0
[1]![]

Try it online!

I gave it a day so I thought I'd give this a spin in Haskell myself. [1]![] gives an infinite list of the results.

edited Jan 12, 2022 at 14:03

answered Jan 12, 2022 at 13:09

Wheat Wizard♦

94.6k19 gold badges266 silver badges625 bronze badges

\$\begingroup\$ 77 bytes \$\endgroup\$
– xnor
Jan 12, 2022 at 13:59

Add a comment |

Neil · Accepted Answer · 2022-01-11 12:55:06Z

Charcoal, 40 bytes

≔¹ηＦＮ«≔¹ζＷ∨№υζ№υ±↔⁻ζη≦⊕ζ⊞υζ⊞υ±↔⁻ζη≔ζη⟦Ｉζ

Try it online! Link is to verbose version of code. Outputs the first n terms. Explanation: Uses @pxeger's trick to avoid keeping track of two sets.

≔¹η

Start with the previous term being 1. This gives a zero difference for the first term, which doesn't conflict with anything else.

ＦＮ«

Process n terms.

≔¹ζ

Start looking for the next term with 1.

Ｗ∨№υζ№υ±↔⁻ζη

While the term, or its negated absolute difference with the previous term, already exists in the predefined empty list, ...

≦⊕ζ

... increment the potential next term.

⊞υζ

Save the term to the predefined empty list.

⊞υ±↔⁻ζη

Save the negated absolute difference to the predefined empty list.

≔ζη

Save the term as the previous term.

⟦Ｉζ

Output the term on its own line.

G B · Accepted Answer · 2022-01-12 15:00:33Z

2

Ruby, 59 56 bytes

a=0,p=1;loop{d=p p;d-=1while[]!=a&s=[p-d,-d*d];p,=a=s|a}

Try it online!

Stolen from pxeger Python answer, and then thanks pxeger again for -2 bytes.

(previously) Ruby, 76 bytes

a,*r=1;loop{r<<a-a=p(1.step.find{|b|q=1;r.all?{|c|[b]&[q-=c,a-c,c+a]==[]}})}

Try it online!

edited Jan 12, 2022 at 15:00

answered Jan 11, 2022 at 14:49

G B

19.9k1 gold badge19 silver badges50 bronze badges

1

\$\begingroup\$ p(d=p) -> d=p p \$\endgroup\$
– pxeger
Jan 11, 2022 at 16:38
\$\begingroup\$ Also you don't need the * at the start \$\endgroup\$
– pxeger
Jan 12, 2022 at 12:52

Add a comment |

Noodle9 · Accepted Answer · 2022-01-12 15:20:51Z

2

C++ (clang), ^{149 \$\cdots\$ 132} 131 bytes

#import<set>
void f(int&n){std::set<int>s;int i,p=n,x;for(n=1;p--;s.insert({n=i,-x*x}))for(i=0;s.count(++i)|s.count(-(x=n-i)*x););}

Try it online!

Uses pxeger's idea from his Python answer so only one std::set is needed.

Inputs an integer \$n\$.
Returns (through re-assignment of the input value) the \$1\$-indexed \$n^{\text{th}}\$ term of the Slater-Valez sequence.

edited Jan 12, 2022 at 15:20

answered Jan 11, 2022 at 23:42

Noodle9

19.5k3 gold badges19 silver badges45 bronze badges

Add a comment |

Stack Exchange Network

Slater-Velez permutation

Task

Example

Test cases

16 Answers 16

Python, 70 bytes

Brachylog, 16 bytes

Explanation

05AB1E, 15 11 bytes

K (ngn/k), 43 bytes

Haskell, 97 bytes

Haskell, 107 bytes

Vyxal, 20 bytes

Explained

Perl 5 List::Util, 64 bytes

R, 76 bytes

APL (Dyalog Unicode), 32 bytes

R, 74 71 70 bytes

JavaScript (V8), 84 bytes

JavaScript (V8), 66 65 bytes

Haskell, 81 77 bytes

Charcoal, 40 bytes

Ruby, 59 56 bytes

(previously) Ruby, 76 bytes

C++ (clang), ^{149 \$\cdots\$ 132} 131 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
permutations
or ask your own question.

Hot Network Questions

Slater-Velez permutation

Task

Example

Test cases

16 Answers 16

Python, 70 bytes

Brachylog, 16 bytes

Explanation

05AB1E, 15 11 bytes

K (ngn/k), 43 bytes

Haskell, 97 bytes

Haskell, 107 bytes

Vyxal, 20 bytes

Explained

Perl 5 List::Util, 64 bytes

R, 76 bytes

APL (Dyalog Unicode), 32 bytes

R, 74 71 70 bytes

JavaScript (V8), 84 bytes

JavaScript (V8), 66 65 bytes

Haskell, 81 77 bytes

Charcoal, 40 bytes

Ruby, 59 56 bytes

(previously) Ruby, 76 bytes

C++ (clang), 149 \$\cdots\$ 132 131 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfsequencepermutations or ask your own question.

Related

Hot Network Questions

C++ (clang), ^{149 \$\cdots\$ 132} 131 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
permutations
or ask your own question.