18
\$\begingroup\$

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 defaults, found in the tag wiki.

This is 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
\$\endgroup\$

16 Answers 16

8
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Nice idea with the negatives! Here's 71 bytes. Might be possible to shorten the initialization. \$\endgroup\$
    – xnor
    Jan 11 at 11:51
  • \$\begingroup\$ Brownie points for golfing my modified print implementation! \$\endgroup\$
    – pxeger
    Jan 11 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 at 12:53
6
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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)
\$\endgroup\$
4
  • 1
    \$\begingroup\$ I think λλû¥+λ«∞sKн works for 11. (λû¥ is shorter than λ¥D(«) \$\endgroup\$
    – ovs
    Jan 11 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\$ Jan 11 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 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\$ Jan 11 at 15:06
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
1
  • 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 at 3:30
3
\$\begingroup\$

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
\$\endgroup\$
0
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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).

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 77 bytes \$\endgroup\$
    – xnor
    Jan 12 at 13:59
2
\$\begingroup\$

Charcoal, 40 bytes

≔¹ηFN«≔¹ζW∨№υζ№υ±↔⁻ζη≦⊕ζ⊞υζ⊞υ±↔⁻ζη≔ζη⟦Iζ

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.

FN«

Process n terms.

≔¹ζ

Start looking for the next term with 1.

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

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.

⟦Iζ

Output the term on its own line.

\$\endgroup\$
2
\$\begingroup\$

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!

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

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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