11
\$\begingroup\$

A073329 is a sequence where the \$n\$th term is the \$n\$th number with exactly \$n\$ distinct prime factors. For example, \$a(3) = 60\$ as the first \$3\$ integers with \$3\$ distinct prime factors are \$30 = 2 \times 3 \times 5\$, \$42 = 2\times3\times7\$ and \$60 = 2^2 \times 3 \times 5\$.

You are to take a positive integer \$n\$ and output the first \$n\$ terms of the sequence. You may assume the input will never exceed the bounds of your language's integers. This is so the shortest code in bytes wins.

The first 10 terms of the sequence are

2, 10, 60, 420, 4290, 53130, 903210, 17687670, 406816410, 11125544430
\$\endgroup\$
4
  • \$\begingroup\$ Limits/bounds?? \$\endgroup\$
    – st0le
    May 16, 2011 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\$ May 16, 2011 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\$ May 17, 2011 at 23:33
  • 1
    \$\begingroup\$ I've edited the challenge to be slightly more up to date, as well as include an example and some relevant tags. Feel free to revert any changes you dislike \$\endgroup\$ Apr 21, 2021 at 22:52

6 Answers 6

2
\$\begingroup\$

Python, 144 chars

R=range
P=[x for x in R(2,99)if all(x%i for i in R(2,x))]
for a in R(input()):
 x=n=0
 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.

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

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) {
            s.add(i);
            t /= i;
            if (t == 1) {
                if (s.size() == n) {
                    if (n == m) {
                        break;
                    }
                    m++;
                }
                t = ++a;
                s.clear();
            }
            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;
}
\$\endgroup\$
5
  • \$\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\$ May 17, 2011 at 4:07
  • \$\begingroup\$ @Gregory look at update \$\endgroup\$
    – cubanacan
    May 17, 2011 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\$ May 23, 2011 at 2:18
  • \$\begingroup\$ @user because of my own misunderstanding of your comment, clarify your request, please \$\endgroup\$
    – cubanacan
    May 23, 2011 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\$ May 23, 2011 at 14:43
2
\$\begingroup\$

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)
                    p[k]++;
        }
        for(int i = 1; i <= 8; i++) {
            int c = 0, j;
            for(j = 1; j < N && c < i; j++)
                if(p[j] == i)
                    c++;
            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.

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

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}
\$\endgroup\$
1
\$\begingroup\$

Jelly, 9 bytes

Æv=¥ḷ#)Ṫ€

Try it online!

How it works

Æv=¥ḷ#)Ṫ€ - Main link. Takes n on the left
      )   - For each integer 1 ≤ k ≤ n, so the following:
   ¥ḷ#    -   Find the first k integers for which the following is true:
Æv        -     The number of distinct prime factors
  =       -     equals k
       Ṫ€ - Return the last element from each list
\$\endgroup\$
0
\$\begingroup\$

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.

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