Composite Number Sequences

Question

_{Inspired by this question}

Given a positive integer \$n\$, your code must output the first \$n\$ composite numbers.

Input / Output

You may write a program or a function. Input is through STDIN or function argument and output is to STDOUT, or function return value.

Output can be a List, Array, or String.

Examples

 0 -> 
 1 -> 4
 2 -> 4, 6
 3 -> 4, 6, 8
13 -> 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22

---

Rules

• As always standard loopholes are disallowed.

• Built-ins that generate prime or composite numbers are not allowed.

• Built-ins relating to prime or composite numbers are not allowed.

Answer 1

Pyth - 10 bytes

A valid answer. Uses Wilson's Theorem.

.f%h.!tZZQ

Try it online here.

Old answer

Pyth - 6 chars

Uses builtin for prime factorization, not prime checking.

.ftPZQ

Try it online here.

.f  Q         First n that passes filter of lambda Z, uses input for how many
 t            Tail. This makes all that have len-one prime factorization become empty list, and thus falsey.
  P           Prime factorization - primes have a len-one factorization.
   Z          Lambda var

Answer 2

Pyth, 11 bytes

<S{*M^tSQ2Q

Generates overly large list of products of all combinations of [2, n] and truncates.

Answer 3

TeX, 382 bytes

Because you can.

\newcount\a\newcount\b\newcount\c\newcount\n\newcount\p\newcount\q\let\v\advance\let\e\else\let\z\ifnum
\def\d#1:#2:#3:{\z#1>#2\v#1 by-#2\d#1:#2:#3:\e\z#1=#2#3=1\e#3=0\fi\fi}
\def\i#1:#2:#3:{#3=0\z#1>#2\a=#1\d\a:#2:\c:
\z\c=0\b=#2\v\b by 1\i#1:\the\b:#3:\e#1\par\fi\e#3=1\fi}
\def\l#1:#2:#3:#4:{\i\the#1:2:#4:
\z#4=0\v#2 by 1\fi\z#2<#3\v#1 by 1\l#1:#2:#3:#4:\fi}
\l\p:\n:10:\q:\end

The number in the last line is the number of composite numbers you want to have.

This is a simple divisor tester. \d checks if #2 divides #1. \i calls \d for all possible dividers (i.e. < #1). \l lists the first #2 numbers for which \i returns 0.

Ungolfed (well, half-golfed) version:

\newcount\a
\newcount\b
\newcount\c
\newcount\n
\newcount\p
\newcount\q

\def\div#1:#2:#3:{%
  \ifnum#1>#2 %
    \advance#1 by-#2 %
    \div#1:#2:#3:%
  \else%
    \ifnum#1=#2 %
      #3=1%
    \else%
      #3=0%
    \fi%
  \fi%
}

\long\def\isprime#1:#2:#3:{%
  #3=0%
  \ifnum#1>#2 %
    \a=#1 %
    \div\a:#2:\c: %
    \ifnum\c=0 %
      \b=#2 %
      \advance\b by 1 %
      \isprime#1:\the\b:#3:%
    \else
      #1\par%
    \fi%
  \else%
    #3=1%
  \fi%
}

\def\listprimes#1:#2:#3:#4:{%
  \isprime\the#1:2:#4: %
  \ifnum#4=0 %
    \advance#2 by 1 %
  \fi
  \ifnum#2<#3 %
    \advance#1 by 1 %
    \listprimes#1:#2:#3:#4: %
  \fi
}

\listprimes\p:\n:11:\q:

\end

Answer 4

Python, 57

lambda n:sorted({(k/n+2)*(k%n+2)for k in range(n*n)})[:n]

Less golfed:

def f(n):
 R=range(n)
 return sorted({(a+2)*(b+2)for a in R for b in R})[:n]

The idea is to generate the set of composite numbers by multiplying all pairs of natural numbers except 0 and 1. Then, sort this set, and take the first n elements. It suffices to take the Cartesian product of the set {2, 3, ..., n+2} with itself, which we can get by shifting range(n) up by 2.

To golf this, we do a classic golfing trick of storing two values (a,b) in range(n) as a single value k in range(n*n), and extract them as a=k/n, b=k%n.

Answer 5

Java 8, 98 97 bytes

i->{int a[]=new int[i],c=3,k=0,d;for(;k<i;c++)for(d=c;d-->2;)if(c%d<1){a[k++]=c;break;}return a;}

Expanded, with boilerplate:

public class C {
    public static void main(String[] args) {
        Function<Integer, int[]> f = i -> {
            int a[] = new int[i], c = 3;
            for (int k = 0; k < i; c++) {
                for (int d = c; d --> 2;) {
                    if (c % d < 1) {
                        a[k++] = c;
                        break;
                    }
                }
            }
            return a;
        };
        System.out.println(Arrays.toString(f.apply(5)));
    }
}

Answer 6

R, 53 bytes

n=scan();t=1:(n*n+3);t[factorial(t-1)%%t!=(t-1)][1:n]

How it works

This is also based on Wilson's theorem and all it does is to run over a range of 1:n*n and extract the composite numbers according to the above mentioned theorem. I've added +3 because n*n isn't big enough range for n < 3 integers

---

The only problem with this solution is that (sadly) R loses precision for a big enough factorial, thus, this won't work properly for n > 19

Answer 7

CJam, 20 18 bytes

li_5*{_,2>f%0&},<`

Try it online

Does not use any built in prime or factorization operators. Fairly brute force check for numbers being composite.

One observation that is used here is that we can easily calculate a safe upper bound for the numbers we have to test. Since every second number larger than 4 is composite, 4 + n * 2 is an upper bound for the n-th composite number.

Based on a suggestion by @Dennis, the latest implementation actually uses n * 5 as the upper limit, which is much less efficient, but 2 bytes shorter.

Explanation:

li    Get and convert input.
_     Copy, will need the value to trim the list at the end.
5*    Calculate upper bound.
{     Start of filter.
  _     Copy value.
  ,     Create list [0 .. value-1].
  2>    Slice off the first two, leaving candidate factors [2 .. value-1].
  f%    Apply modulo with all candidate factors to value.
  0&    Check if one of the modulo results is 0.
},    End of filter.
<     Trim output to n values.
`     Convert list to string.

Answer 8

Javascript ES6, 88 chars

n=>{r=[];for(q=2;r.length!=n;++q)if(/^(..+)\1+$/.test("-".repeat(q)))r.push(q);return r}

Answer 9

Haskell, 49 46 bytes

(`take`[x|x<-[4..],or[mod x y<1|y<-[2..x-1]]])

Usage example:

*Main> (`take`[x|x<-[4..],or[mod x y<1|y<-[2..x-1]]]) 13
[4,6,8,9,10,12,14,15,16,18,20,21,22]

How it works

  [x|x<-[4..]    ]           -- keep all x from the integers starting with 4 where
      ,or                    -- where at least one element of the following list is "True"
    [mod x y<1|y<-[2..x-1]]  -- "x mod y < 1" for all y from [2,3,...x-1]
(`take`[   ])                -- take the first n elements from the xes
                             -- where n is the parameter supplied when calling the function

Answer 10

F#, 78 bytes

fun n->(Array.filter(fun i->Seq.exists((%)i>>(=)0)[2..i-1])[|2..n*n|]).[..n-1]

Explained:

fun n->                                                                      
                                                           [|2..n*n|]          // Generate an array of integers from 2 to n * n
        Array.filter(fun i->                              )                    // Filter it using the following function on each element
                                                  [2..i-1]                        // Generate a list of possible divisors (from 2 to i-1)
                            Seq.exists(          )                                // Check if at least one of the divisors is valid, that is
                                       (%)i>>(=)0                                    // That i % it is equal to 0. This is equivalent to (fun d -> i % d = 0)
       (                                                             ).[..n-1] // Take the n first elements of the resulting, filtered array

Answer 11

C++ 109

int main(){int n,i,x=4;cin>>n;while(n){for(i=2;i<x-1;i++){if(x%i==0){cout<<x<<' ';n--;break;}}x++;}return 0;}

Ungolfed

int main(){
int n,i,x=4;cin>>n;
while(n)
{
for(i=2;i<x-1;i++)
{
if(x%i==0){cout<<x<<' ';n--;break;}
}
x++;
}
return 0;
}

Answer 12

Julia, 103 bytes

n->(n>0&&println(4);n>1&&(i=0;c=big(6);while i<n-1 mod(factorial(c-1),c)<1&&(i+=1;println(c));c+=1end))

This uses Wilson's Theorem.

Ungolfed:

function f(n::Int)
    # Always start with 4
    n > 0 && println(4)

    # Loop until we encounter n composites
    if n > 1
        i = 0
        c = big(6)
        while i < n-1
            if mod(factorial(c-1), c) == 0
                i += 1
                println(c)
            end
            c += 1
        end
    end
end

Answer 13

ECMAScript 6 – 107 91 84 bytes

n=>eval('for(a=[],x=4;n&&!a[~-n];x++)for(y=2;y*2<=x;)if(x%y++<1){a.push(x);break}a')

The function returns an array of the first n composite numbers.

~-n is a fancy way of writing n-1; same length, but much more fun, right?
The only reason I use eval is that the template n=>eval('...returnValue') is 1 character shorter than n=>{...return returnValue}.

Old versions

n=>eval('for(a=[],x=4;n&&!a[~-n];x++){for(z=0,y=2;y*2<=x;)if(x%y++<1)z=1;if(z)a.push(x)}a')

---

n=>eval('for(a=[],i=4;a.length<n;i++)if((x=>{for(y=2,z=1;y*2<=x;)if(x%y++<1)z=0;return!z})(i))a.push(i);a')

Output

 0 -> []
 1 -> [4]
 2 -> [4, 6]
 3 -> [4, 6, 8]
13 -> [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22]

Answer 14

Haskell, 44 bytes

Heavily inspired by Nimi's earlier answer, replacing the predicate with a 2-byte shorter one based on any with a pointfree lambda instead of a nested list comprehension.

(`take`[x|x<-[4..],any((<)1.gcd x)[2..x-1]])

Try it online!
(thanks to Laikoni for the accurate TIO link)

Explanation:

[x|x<-[4..],       -- consider all integers x >=4
[2..x-1]           -- consider all integers smaller than x
any((<)1.gcd x)    -- if for any of them 
    (<)1           -- 1 is smaller than
        .gcd x     -- the gcd of x and the lambda input
                   -- then we found a non-trivial factor and thus the number is composite
(`take`[  ])       -- take the first <argument> entries

Answer 15

Husk, ¹⁴ 12 bytes

↑fṠöV¬thM%ḣN

Try it online!

-2 bytes from Jo King.

Husk, 8 bytes

↑fȯ≠2LḊN

Try it online!

Uses the Ḋivisors function, if that is okay.

Answer 16

Japt, 9 bytes

Èâ ʨ3}jU

Try it

Answer 17

Vyxal, 7 bytes

∞'KḢḢ;Ẏ

Try it Online!

∞       # The set of all positive integers
 '   ;  # Filtered by...
  K     # The list of factors of n
   ḢḢ   # Has length > 2
      Ẏ # Get first n

Using a isprime builtin doesn't actually save any bytes as 1 and 0 are considered nonprime.