Composite Number Sequences

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.

14 Answers 14

up vote 11 down vote accepted

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
  • Hm, should of thought about that :/ – Downgoat Sep 8 '15 at 3:44
  • 1
    The rules have changed and thus this answer is no longer valid. – orlp Sep 8 '15 at 4:18
  • @orlp updated answer. – Maltysen Sep 8 '15 at 5:10
  • @Maltysen Isn't this 10 bytes? – kirbyfan64sos Sep 8 '15 at 18:35
  • @kirbyfan64sos :/ I apparently can't read the length counter. Fixing. – Maltysen Sep 9 '15 at 2:28

Pyth, 11 bytes

<S{*M^tSQ2Q

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

  • It does not work if the input is 1 or 2. – Toothbrush Sep 10 '15 at 20:52

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
  • 1
    Welcome to Programming Puzzles and Code Golf! Great first answer in a language nobody thought would be suitable for the challenge. Although it is pretty long, it is unique and neat answering in TeX and we certainly appreciate such answers. – TanMath Jan 25 '16 at 10:29
  • 1
    @TanMath thanks for the warm welcome, I realize this is too long to compete, but it was fun :) – Keelan Jan 25 '16 at 10:29

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.

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

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

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.

Javascript ES6, 88 chars

n=>{r=[];for(q=2;r.length!=n;++q)if(/^(..+)\1+$/.test("-".repeat(q)))r.push(q);return r}
  • I believe removing the variable assignment f= is legal. – DankMemes Sep 8 '15 at 14:11
  • @DankMemes, seems yes. meta.codegolf.stackexchange.com/q/6915/32091 – Qwertiy Sep 8 '15 at 14:17
  • 1
    This is 83: n=>eval('for(r=[],q=2;r.length-n;/^(..+)\\1+$/.test("-".repeat(++q))&&r.push(q))r') – DankMemes Sep 8 '15 at 14:29
  • @DankMemes, cool :) – Qwertiy Sep 8 '15 at 14:32
  • 1
    @Qwertiy Sorry, I meant n&&!r[n-1] :'| It is the same length as r.length<n – one character shorter than r.length!=n – but this is supposed to be Code Golf, right? :-] – Toothbrush Sep 10 '15 at 19:59

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

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
  • 1
    This is a great answer, however it is a bit confusing that you use the variable i twice. I'm not too familiar with F#, but couldn't you perhaps use j? – wizzwizz4 Jan 25 '16 at 19:10
  • Right, that does make it clearer. It did work due to shadowing, but I guess I forgot about readability while golfing the thing. ^_^' – Roujo Jan 25 '16 at 19:21
  • I don't ever make that sort of mistake. Probably why I'm not good at golfing d:-D – wizzwizz4 Jan 25 '16 at 19:29

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;
}
  • 1. Why not make a nice formatting for ungolfed version? 2. Seems like you have extra braces in both codes. 3. You can replace while by for. – Qwertiy Sep 8 '15 at 14:20

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

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]

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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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