Formerly Composite Numbers

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.
• Title: The number formerly known as composite. – Magic Octopus Urn Feb 14 '18 at 16:53
• @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. – AdmBorkBork Feb 14 '18 at 17:02
• Was more of a joke ;). – Magic Octopus Urn Feb 14 '18 at 17:03

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.


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
}


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!

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


05AB1E, 21 bytes

0-indexed

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


Try it online!

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!

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;}


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
}


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!

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!

• ++k,j=0 can twice be j=!++k, 138 bytes. – Jonathan Frech Mar 9 '18 at 23:31