23
\$\begingroup\$

(This is A065825.) The defaults apply, so you can pick another format other than this one.

Given an input integer n, find the smallest number k so that there exists an n-item subset of {1,...,k} where no three items form an arithmetic progression.

Procedure

Here, we calculate A065825(9).

We assume you have already looped from 1 to 19, and k=20 (it's just an example).

1. Generate a range from 1 to k.

[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]

2. Pick n items from that sequence, following the original order of the sequence.

[1 2 6 7 9 14 15 18 20]

3. No 3 items form an arithmetic progression.

If a sequence has arithmetic progression, it basically means the sequence has the same step between every two consecutive items.

For example, the sequence of positive even numbers ([2 4 6 8 ...]) has a consistent step (i.e. 4-2=2, and 6-4=2, etc.), so it has arithmetic progression.

The Fibonacci sequence ([1 1 2 3 5 8 13 21 ...]) does not have arithmetic progression, since it does not have a consistent step. (3-2=1, 5-3=2, 8-5=3, etc.)

As an example, let's pick 3 items from our generated sequence.

[1 2 6 [7 9 14] 15 18 20]

The picked 3-item sequence does not have arithmetic progression, since the differences are respectively 9-7=2 and 14-9=5.

This has to apply to every 3-item pair:

[[1 2 6] 7 9 14 15 18 20] (2 -1 =1, 6 -2 =4)
[1 [2 6 7] 9 14 15 18 20] (6 -2 =4, 7 -6 =1)
[1 2 [6 7 9] 14 15 18 20] (7 -6 =1, 9 -7 =2)
[1 2 6 [7 9 14] 15 18 20] (9 -7 =2, 14-9 =5)
[1 2 6 7 [9 14 15] 18 20] (14-9 =5, 15-14=1)
[1 2 6 7 9 [14 15 18] 20] (15-14=1, 18-15=3)
[1 2 6 7 9 14 [15 18 20]] (18-15=3, 20-18=2)

Here are some examples of picking non-consecutive items from the output sequence:

[1 [2] 6 [7] 9 [14] 15 18 20] (7-2=5,14-7=7)
[[1] 2 6 [7] [9] 14 15 18 20] (7-1=6,9 -7=2)

If the above is satisfied for k, then k is a valid output for A065825(9).

Test cases

Here is a reference program I use to check my test cases.

n       a(n)
1       1
2       2
3       4
4       5
5       9
6       11
7       13
8       14
9       20
\$\endgroup\$
  • 2
    \$\begingroup\$ Since this sequence runs into performance issues really fast, it could be interesting to repost this question with a [fastest-code] tag. Either who beats the a(43) (highest n) currently on OEIS or who calculates a(n) fastest for a n somewhere in the n=25 to 35 range... Just a suggestion... \$\endgroup\$ – agtoever Apr 30 at 17:47

11 Answers 11

3
\$\begingroup\$

Jelly, 14 bytes

œcœc3IEƇƊÐḟð1#

A monadic Link accepting a non-negative integer which yields a non-negative integer.

Try it online! (Too inefficient for n=9 within 60s.) Or see the test-suite.

How?

œcœc3IEƇƊÐḟð1# - Link: integer, n
            1# - let k=n and count up to find the first k, for which this is truthy:
           ð   -   dyadic chain - i.e. f(k, n):
œc             -     combinations of length (n) of (implicit [1..k])
         Ðḟ    -     filter discard those n-tuples which are truthy under:
        Ɗ      -       last three links as a monad:
  œc3          -         combinations of length three of (the n-tuple)
     I         -         incremental differences - e.g. [3,6,8]->[6-3,8-6]->[3,2]
       Ƈ       -         filter keep those diffence-pairs which are truthy under:
      E        -           all equal?
| improve this answer | |
\$\endgroup\$
9
\$\begingroup\$

Pyth, 17 bytes

ff!/#.OZ.cY3.cSTQ

Try it online!

.cSTQ: generate all list of numbers in the range [1,T] with length equal to the input.

.cY3: for each of those, generate all length 3 subsequences.

/#.OZ: filter for the subsequences where the average is a member of the list. These are the arithmetic progressions.

f!: filter for the original lists with no arithmetic progressions

f: find the lowest T where at least one list is found.

| improve this answer | |
\$\endgroup\$
7
\$\begingroup\$

Python 3.8, 123 115 96 94 bytes

Another -15 -17 bytes thanks to Surcolose Sputum!

f=lambda n,k=1:len(d:=f'{k:b}')*all(k>>i&k&k<<i<1for i in range(d.count('1')//n,k))or f(n,k+1)

Try it online!


Python 2, 147 135 124 bytes

-11 bytes thanks to Surcolose Sputum!

from itertools import*
f=lambda n,k=1,C=combinations:k*any(all(a+c-b*2for a,b,c in C(w,3))for w in C(range(k),n))or f(n,k+1)

Try it online!

| improve this answer | |
\$\endgroup\$
  • 3
    \$\begingroup\$ 124 bytes as a recursive function \$\endgroup\$ – Surculose Sputum Apr 29 at 14:19
  • \$\begingroup\$ @SurculoseSputum thanks a lot. this looks really compact now. \$\endgroup\$ – ovs Apr 29 at 14:42
  • 1
    \$\begingroup\$ Nice! Since we're already using bit masks, it'd be a shame not to take advantage of some more bit-wise operations. 100 bytes \$\endgroup\$ – Surculose Sputum Apr 29 at 16:43
  • 1
    \$\begingroup\$ No problem. Also I really like how you put the bit count as the start of range, using the fact that k&k<<i&k<<i*2<1 is false when i==0. Very clever! \$\endgroup\$ – Surculose Sputum Apr 29 at 16:50
  • 1
    \$\begingroup\$ Using k<<i&k&k>>i<1 instead saves 2 bytes. Try it online! \$\endgroup\$ – Surculose Sputum Apr 30 at 16:29
6
\$\begingroup\$

R, 96 83 bytes

k=n=scan();C=combn;`[`=Map;try(while(!any(all[diff[C[C(1:k,n,,F),3],1,2]]))k=k+1);k

Try it online!

Full program, returns 1-indexed member of the sequence. Very slow for n > 8.

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

05AB1E, 19 bytes

∞.ΔLI.Æε3.Æε¥Ë≠}P}à

Outputs the \$n^{th}\$ value \$k\$.

Try it online or verify the first 8 test cases (times out for \$\geq9\$).

Explanation:

∞.Δ                 # Find the first positive integer `k`
   L                # for which its list in the range [1,k]
    I.Æ             # with combinations of the input amount of elements
       ε         }à # contains any combination-list which is truthy for:
        3.Æ         #  When taking all 3-element combinations of the current list
           ε   }P   #  they are all truthy for:
            ¥       #   When taking the forward differences of both pairs in this triplet
             Ë≠     #   they are NOT the same
                    # (after which the resulting `k` is output implicitly)
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

Ruby, 109...94 91 bytes

-8 bytes thanks to @GB

->n{1.step.find{|k|[*1..k].combination(n).any?{|p|p.combination(3).all?{|a,b,c|b-a!=c-b}}}}

Try it online! Takes less than 1 s for \$n\le9\$. Times out for \$n\ge12\$.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Nice, but maybe use 1.step.find instead of relying on the exit code, this makes it shorter and you can print the result on TIO. \$\endgroup\$ – G B Apr 29 at 16:47
  • 1
    \$\begingroup\$ Also, instead of .map{...}.all? you could just use .all?{...} \$\endgroup\$ – G B Apr 29 at 16:57
3
\$\begingroup\$

Wolfram Language (Mathematica), 94 bytes

(t=1;While[Select[Range@t++~(S=Subsets)~{#},!Or@@(Equal@@Differences@#&/@#~S~{3})&]=={}];t-1)&

Try it online! 1-9 takes 1 min

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6),  150  145 bytes

This is quite inefficient for \$n>8\$.

n=>(g=a=>(P=a=>a.reduce((a,x)=>[...a,...a.map(y=>[...y,x])],[[]]))(a).some(a=>a[n-1]*P(a).every(([a,b,c,d])=>d|b-a!=c-b))?k:g([...a,++k]))([k=1])

Try it online!

Commented

Helper function

Since we don't have any combinatorial function available as a built-in, we're going to define just one: \$P\$ is a helper function that computes the powerset of a given array.

P = a =>
  a.reduce((a, x) =>
    [...a, ...a.map(y => [...y, x])],
    [[]]
  )

Main function

n => (                  // n = input
  g = a =>              // g is a recursive function taking a range a[]:
    P(a).some(a =>      //   for each array a[] in the powerset of a[]:
      a[n - 1] *        //     make sure that the length of a[] is at least n
      P(a)              //     compute the powerset of a[]
      .every(           //     for each quad [a,b,c,d] in there,
      ([a, b, c, d]) => //     the test is successful if either:
        d |             //       - d is defined (meaning that this array has
                        //         more than 3 entries)
        b - a != c - b  //       - or a,b,c is not an arithmetic progression
      )                 //     end of every()
    )                   //   end of some()
    ?                   //   if truthy:
      k                 //     success: return k
    :                   //   else:
      g([...a, ++k])    //     try again with k+1 appended to a[]
)([k = 1])              // initial call to g with k = 1 and a = [1]
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

MATL, 22 bytes

`@:GXN!"@IXN!ddA]va~}@

Try it online! Or verify test cases 18 (test case 9 times out online).

Explanation

`       % Do...while
  @:    %   Push range [1 2 ... k] where is the current iteration index
  G     %   Push input, n
  XN    %   Combinations of the elements [1 2 ... k] taken n at a time. This
        %   gives an n-column matrix where each row is a combination
  !     %   Transpose. Each combination is now a column
  "     %   For each column
    @   %     Push current column
    I   %     Push 3
    XN  %     Combinations of the elements of the current column taken n at
        %     a time. This gives a 3-column matrix
    !   %     Transpose. Each combination is now a column
    dd  %     Consecutive differences along each column, twice. This gives a
        %     row vector containing 0 for columns whose three elements form
        %     an arithmetic progression
    A   %     All. This gives true if all entries of the vector are non-zero;
        %     that is, if there were no arithmetic progressions of length 3
  ]     %   End
  v     %   Concatenate the stack into a column vector
  a~    %   Any, negate. Gives false if any entry from the above vector is
        %   non-zero. This will be used as loop condition; that is, if false
        %   the loop will end
}       % Finally (execute on loop break)
  @     %   Push latest k
        % End (implicit). The top of the stack is used as loop condiion
        % Display (implicit)
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 40 37 bytes

≔⁰ηW∨⁻Σ⍘η²IθΦη&η&×ηX²⊕λ×ηX⁴⊕λ≦⊕ηIL↨η²

Try it online! Link is to verbose version of code. Edit: Saved 3 byte by porting @SurculoseSputum's method. Now too slow for n>6. Explanation:

≔⁰η

Start with an empty bitmask.

W∨⁻Σ⍘η²Iθ

Repeat while the bitmask contains the wrong number of bits...

Φη&η&×ηX²⊕λ×ηX⁴⊕λ

... or it contains three terms in arithmetic progression...

≦⊕η

... increment the bitmask.

IL↨η²

Output the the length (in base 2) of the bitmask, which is necessarily equal to k.

At a cost of 2 bytes, I can replace Φη with ⊙↨η², which makes the code fast enough to compute up to n=9:

≔⁰ηW∨⁻Σ⍘η²Iθ⊙↨η²&η&×ηX²⊕λ×ηX⁴⊕λ≦⊕ηIL↨η²

Try it online! Link is to verbose version of code. (Link only computes n=8 to avoid unnecessarily overloading TIO.)

Looping over the odd numbers is slightly faster still, but not enough to be able to compute n>9 on TIO. (It also gives the wrong answer for n=0, although that's not required by the question.)

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Retina, 91 bytes

.+
*_¶
/^(_)*¶(?<-1>10*)*(?(1)$|1)|1(.)*1(?<-2>.)*(?(2)$)1/{`¶(1*)$
¶0$1
)T`10`d`01*$
r`.\G

Try it online! Uses @SurculoseSputum's method, but too slow for n>8. Explanation:

.+
*_¶

Convert n to unary, and add a working area for the bitmask.

/^(_)*¶(?<-1>10*)*(?(1)$|1)|1(.)*1(?<-2>.)*(?(2)$)1/{`
)`

Repeat while the number of bits in the bitmask is not n, or there are three bits in the bitmask with identical spacing...

¶(1*)$
¶0$1

If the bitmask contains no zeros then prefix one.

T`10`d`01*$

Increment the bitmask.

r`.\G

Output the length of the bitmask, which is necessarily equal to k.

The bitmask computations involve .NET balancing groups.

^(_)*¶

This captures the unary value of n. Since the * is outside of the (_), the group is captured n times. .NET records each capture as a stack, so $1 now has a depth of n.

(?<-1>10*)*

This attempts to match the regex 10*. Each successful match pops one of the captures from the $1 stack. This continues until the stack is empty or there are no matches.

(?(1)$|1)

A conditional expression now checks whether the stack is empty. If it is not, then we want this to be because we ran out of 1 bits to match, which will be at the end of the string. If the stack is empty, then we want this to be because there are too many 1 bits, so we should be able to match one.

Note that while Retina will try to backtrack if it fails to match, this necessarily means both that the stack is not empty and that the match is not at the end of the string, i.e. this condition will never succeed in the case where the number of bits is correct.

1(.)*1(?<-2>.)*(?(2)$)1

In a similar way, we capture a variable number of bits between two 1 bits, and then require that the same number of bits exists between the latter and another 1 bits. Here the condition for a non-empty stack is a logical impossibility ($ before a 1) thus requiring the stack to be empty at this point, indicating that the number of bits is the same.

| improve this answer | |
\$\endgroup\$

Your Answer

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