16
\$\begingroup\$

Sequence Definition

Construct a sequence of positive integers a(n) as follows:

  1. a(0) = 4
  2. Each term a(n), other than the first, is the smallest number that satisfies the following:
    a) a(n) is a composite number,
    b) a(n) > a(n-1), and
    c) a(n) + a(k) + 1 is a composite number for each 0 <= k < n.

So we start with a(0) = 4. The next entry, a(1) must be 9. It can't be 5 or 7 since those aren't composite, and it can't be 6 or 8 because 6+4+1=11 is not composite and 8+4+1=13 is not composite. Finally, 9+4+1=14, which is composite, so a(1) = 9.

The next entry, a(2) must be 10, since it's the smallest number larger than 9 with 10+9+1=20 and 10+4+1=15 both composite.

For the next entry, 11 and 13 are both out because they're not composite. 12 is out because 12+4+1=17 which is not composite. 14 is out because 14+4+1=19 which is not composite. Thus, 15 is the next term of the sequence because 15 is composite and 15+4+1=20, 15+9+1=25, and 15+10+1=26 are all each composite, so a(3) = 15.

Here are the first 30 terms in this sequence:

4, 9, 10, 15, 16, 22, 28, 34, 35, 39, 40, 46, 52, 58, 64, 70, 75, 76, 82, 88, 94, 100, 106, 112, 118, 119, 124, 125, 130, 136

This is OEIS A133764.

Challenge

Given an input integer n, output the nth term in this sequence.

Rules

  • You can choose either 0- or 1-based indexing. Please state which in your submission.
  • The input and output can be assumed to fit in your language's native integer type.
  • The input and output can be given by any convenient method.
  • Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.
\$\endgroup\$
  • 3
    \$\begingroup\$ Title: The number formerly known as composite. \$\endgroup\$ – Magic Octopus Urn Feb 14 '18 at 16:53
  • \$\begingroup\$ @MagicOctopusUrn If this had something to do with art or music, I'd go with it. But, I'll stick with the title I currently have. \$\endgroup\$ – AdmBorkBork Feb 14 '18 at 17:02
  • \$\begingroup\$ Was more of a joke ;). \$\endgroup\$ – Magic Octopus Urn Feb 14 '18 at 17:03

10 Answers 10

5
\$\begingroup\$

Husk, 11 bytes

!üȯṗ→+fotpN

1-indexed. Try it online!

Explanation

!üȯṗ→+fotpN  Implicit input, a number n.
          N  The list of positive integers [1,2,3,4,..
      f      Keep those
         p   whose list of prime factors
       ot    has a nonempty tail: [4,6,8,9,10,12,..
 ü           De-duplicate wrt this equality predicate:
     +       sum
    →        plus 1
  ȯṗ         is a prime number.
             Result is [4,9,10,15,16,..
!            Get n'th element.
\$\endgroup\$
2
\$\begingroup\$

Perl 6, 70 bytes

{(4,->+_{first {none($^a X+0,|(_ X+1)).is-prime},_.tail^..*}...*)[$_]}

Try it 0-indexed

Expanded:

{  # bare block lambda with implicit parameter $_

  (  # generate the sequence

    4, # seed the sequence

    -> +_ { # pointy block that has a slurpy list parameter _ (all previous values)

      first

      {  # bare block with placeholder parameter $a

        none(                 # none junction
            $^a               # placeholder parameter for this inner block
          X+                
            0,                # make sure $a isn't prime
            |( _ X+ 1 )       # check all a(k)+1
        ).is-prime            # make sure none are prime
      },

      _.tail ^.. *            # start looking after the previous value
    }

    ...                       # keep generating values until

    *                         # never stop

  )[$_]                       # index into the sequence
}
\$\endgroup\$
2
\$\begingroup\$

Python 2, 112 107 bytes

thanks to Mr. Xcoder for a byte.

n=-1,4;v=5
exec"while any(all((v-~k)%i for i in range(2,v))for k in n):v+=1\nn+=v,;v+=1\n"*input()
print~-v

Try it online!


Python 2, 115 109 bytes

n=-1,4;v=4;x=input()
while x:v+=1;k=1^any(all((v-~k)%i for i in range(2,v))for k in n);n+=(v,)*k;x-=k
print v

Try it online!

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

JavaScript (ES6), 83 bytes

1-indexed

f=(n,a=[-1,p=4])=>a[n]||f(n,a.some(x=>(P=n=>n%--x?P(n):x<2)(x-=~p),p++)?a:[...a,p])

Demo

f=(n,a=[-1,p=4])=>a[n]||f(n,a.some(x=>(P=n=>n%--x?P(n):x<2)(x-=~p),p++)?a:[...a,p])

for(n = 1; n <= 30; n++) {
  console.log('a(' + n + ') = ' + f(n))
}

Commented

Helper function P(), returning true if n is prime, or false otherwise:

P = n => n % --x ? P(n) : x < 2

NB: It must be called with x = n.

Main function f():

f = (               // given:
  n,                //   n = target index
  a = [-1, p = 4]   //   a = computed sequence with an extra -1 at the beginning
) =>                //   p = last appended value
  a[n] ||           // if a[n] exists, stop recursion and return it
  f(                // otherwise, do a recursive call to f() with:
    n,              //   n unchanged
    a.some(x =>     //   for each value x in a[]:
      P(x -= ~p),   //     rule c: check whether x + p + 1 is prime
                    //     rule a: because a[0] = -1, this will first compute P(p)
      p++           //     rule b: increment p before the some() loop starts
    ) ?             //   end of some(); if truthy:
      a             //     p is invalid: use a[] unchanged
    :               //   else:
      [...a, p]     //     p is valid: append it to a[]
  )                 // end of recursive call
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 21 bytes

0-indexed

®4Iµ)˜D¤N‹sN+>p_P*iN¼

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 65 bytes

±0=-1;±1=4;±n_:=±(n-1)+1//.a_/;PrimeQ/@Array[a+1+±#&,n,0,Or]:>a+1

Uses CP-1252 (default Windows) encoding. 1-indexed.

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Java 8, 186 173 bytes

n->{int a[]=new int[n+1],r=a[n]=4;a:for(;n>0;)if(c(++r)<2){for(int x:a)if(x>0&c(r-~x)>1)continue a;a[--n]=r;}return r;}int c(int n){for(int i=2;i<n;n=n%i++<1?0:n);return n;}

0-indexed.
Unfortunately prime-checks (or anti-prime/composite checks in this case) aren't that cheap in Java..

Explanation:

Try it online.

n->{                     // Method with integer as both parameter and return-type
  int a[]=new int[n+1],  //  Integer-array of size `n+1`
      r=a[n]=4;          //  Start the result and last item at 4
  a:for(;n>0;)           //  Loop as long as `n` is larger than 0
    if(c(++r)<2){        //   Raise `r` by 1, and if it's a composite:
      for(int x:a)       //    Inner loop over the array
        if(x>0           //     If the item in the array is filled in (non-zero),
           &c(r-~x)>1)   //     and if `r+x+1` is a prime (not a composite number):
          continue a;}   //      Continue the outer loop
      a[--n]=r;}         //    Decrease `n` by 1, and put `r` in the array
  return r;}             //  Return the result

// Separated method to check if a given number is a composite number
// (It's a composite number if 0 or 1 is returned, otherwise it's a prime.)
int c(int n){for(int i=2;i<n;n=n%i++<1?0:n);return n;}
\$\endgroup\$
0
\$\begingroup\$

Ruby + -rprime, 85 75 bytes

->n{*a=x=4
n.times{x+=1;!x.prime?&&a.none?{|k|(x+k+1).prime?}?a<<x:redo}
x}

Try it online!

A lambda returning the 0-indexed nth element.

-10 bytes: Use redo and a ternary operator instead of loop...break and a conditional chain

Ungolfed:

->n{
  *a=x=4                         # x is the most recent value: 4
                                 # a is the list of values so far: [4]
  n.times{                       # Repeat n times:
    x += 1                       # Increment x
    !x.prime? &&                 # If x is composite, and
      a.none?{|k|(x+k+1).prime?} #   for all k, a(n)+x+1 is composite,
      ? a<<x                     # Add x to a
      : redo                     # Else, restart the block (go to x+=1)
  }
  x                              # Return the most recent value
}
\$\endgroup\$
0
\$\begingroup\$

C (gcc), 170 bytes

P(n,d,b){for(b=d=n>1;++d<n;)b=b&&n%d;n=b;}h(n,N,b,k){if(!n)return 4;for(b=N=h(n-1);b;)for(b=k=!N++;k<n;b|=P(h(k++)-~N));n=N;}f(n,j){for(j=0;n--;)if(P(h(++j)))j++;n=h(j);}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

C (gcc),  140  138 bytes

Thanks to @Jonathan Frech for saving two bytes!

c(n,i){for(i=1;++i<n;)i=n%i?i:n;i=i>n;}f(n){int s[n],k,j,i=0;for(*s=k=4;i++-n;i[s]=k)for(j=!++k;j-i;)2-c(k)-c(k-~s[j++])?j=!++k:f;n=n[s];}

0-indexed

Try it online!

\$\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.