Create the shortest function, program, or expression that calculates A073329, i.e., a(n) is the nth number having n distinct prime factors. Input is the number of elements in the sequence to return. 0 < n. I am unconcerned with integer precision. I just want the algorithm. For languages that don't support arbitrarily large integers, we'll just pretend they do.

You can find test cases by following the link to OEIS given above.


Let me make it clear that you need to return an integer sequence from your program, function, or expression. In other words, f(x) should calculate a(n) for all n from 1 to x. Given x of 8, your function should return 2, 10, 60, 420, 4290, 53130, 903210, 17687670 as an array or some other appropriate data structure.

  • \$\begingroup\$ Limits/bounds?? \$\endgroup\$ – st0le May 16 '11 at 5:35
  • \$\begingroup\$ I'm not really concerned with limits and bounds, but if it's important to you, do the algorithm assuming the input will be no more than 8, and we'll pretend it works for higher numbers. As I said, I'm interested in the abstract mathematical algorithm, not the details of a particular language's integer limitations. \$\endgroup\$ – Gregory Higley May 16 '11 at 12:57
  • 1
    \$\begingroup\$ Maybe it is more open, when we say: output a(1), ... a(n) instead of return something, like an array of ... \$\endgroup\$ – user unknown May 17 '11 at 23:33

Python, 144 chars

P=[x for x in R(2,99)if all(x%i for i in R(2,x))]
for a in R(input()):
 while n<=a:n+=sum(x%p==0for p in P)==a+1;x+=1
 print x-1

It takes about 2 minutes to run to completion for x=8.


Java, 170 characters in one line

int a(int n) {
    int a = 2, t = a, m = 1, i = 1;
    Set s = new HashSet();
    while (i++ > 0) {
        if (t % i == 0) {
            t /= i;
            if (t == 1) {
                if (s.size() == n) {
                    if (n == m) {
                t = ++a;
            i = 1;
    return a;

Update, +77 characters IOL

int[] f(int n) {
    int[] f = new int[n];
    for (int i = 0; i < n; i++) {
        f[i] = a(i+1);
    return f;
  • \$\begingroup\$ This is actually incorrect, but close, though I think I should perhaps make my question clearer. You should be returning an integer sequence. For instance, if the input 8, you should return the first 8 elements in the A073329 sequence. \$\endgroup\$ – Gregory Higley May 17 '11 at 4:07
  • \$\begingroup\$ @Gregory look at update \$\endgroup\$ – cubanacan May 17 '11 at 7:33
  • \$\begingroup\$ I'm sorry - I voted you down, based on my own misunderstanding of the task, which clarified after reading the OEIS-link. If you do a minor edit of your post, I can and will revoke my downvote. \$\endgroup\$ – user unknown May 23 '11 at 2:18
  • \$\begingroup\$ @user because of my own misunderstanding of your comment, clarify your request, please \$\endgroup\$ – cubanacan May 23 '11 at 7:33
  • \$\begingroup\$ I misunderstood the question, and thought, all factors must be distinct primes, so 2*3*5*2 would be a wrong answer. So I voted your answer down for beeing false. Then I discovered, how 'distinct primes' is to understand, and wanted to correct my voting, but I'm not allowed to change my vote - it's only possible in the first, few minutes. But if you edit your answer, I can change my vote. So I'm asking you to edit just a little bit. \$\endgroup\$ – user unknown May 23 '11 at 14:43

Java (Ungolfed)

public class M {

    public static void main(String[] a) {
        final int N = 100000000;
        int[] p = new int[N];
        for(int f = 2; f * f < N; f++) {
            if(p[f] == 0)
                for(int k = f; k < N; k += f)
        for(int i = 1; i <= 8; i++) {
            int c = 0, j;
            for(j = 1; j < N && c < i; j++)
                if(p[j] == i)
            if(c == i)
                System.out.println(i + " = " + --j);

Uses a sieve algorithm. It's pretty quick. (6 Seconds) Will work accurately for upto 8, will probably fail for anything higher.


JavaScript, 149 chars

function(n){function f(x){for(r=[],o=x,z=2;z<=o;x%z?++z:(x/=z,r.indexOf(z)+1?0:r.push(z)));return r}for(c=0,i=1;c<n;)f(++i).length==n?c++:0;return i}

Feels unresponsive for n >= 6 so I haven't tested how long it takes (my browser pops up a hung script notification every 10 seconds or so therefore I can't time it accurately and I don't want to completely hang if I check "don't show this again"...)

Edit: To return array is 200 characters (+51):

function(n){function F(){function f(x){for(r=[],o=x,z=2;z<=o;x%z?++z:(x/=z,r.indexOf(z)+1?0:r.push(z)));return r}for(c=0,i=1;c<n;)F(++i).length==n?c++:0;return i}for(a=[];n>0;n--)a.push(f());return a}

J, 32 bytes

({"0 1~i.@#)(]/.~#@~.@q:)

But since I'm answering my own question so late, we'll just leave this answer as a curiosity.


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.