Passing condition

Computer Science Level 4

A number is said to be fine if the first 4 prime numbers i.e 2, 3, 5, or 7 are its only prime factors.

What is the 4000th fine number?

Details and Assumptions :

As an explicit example the first few fine numbers are 2, 3, 4, 5, 6,7, 8, 9, 10, 12.


The answer is 228709656.

View wiki
Beakal Tiliksew by Beakal Tiliksew , 24, Ethiopia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

5 solutions

Thaddeus Abiy
Jul 27, 2015

Sleep deprivation hopefully excuses ugly one liners. 

1
2
 
from itertools import *
print sorted([2**a*3**b*5**c*7**d for a,b,c,d in product(range(28),repeat=4)])[4000]

Note:

This is not an actual solution. An actual solution would be to notice that a fine number is simply a variation of a Hamming Number . This is a classic CS problem. Clever and efficient algorithms for generating these numbers have been extensively discussed.

4 Helpful 0 Interesting 0 Brilliant 0 Confused

Perhaps I am being dense, but I don't see where the literal value '28' comes from in your range definition above. Doesn't that mean you will have a list with 28^4 (or ~600k) terms in it? Is that just a value that you are sure MUST be "big enough", because it seems way too big to me. I used an iterative method that kept adding the next Hamming-like sequence to the list and resorting, checking to see if the ordering of the first 4000 elements had changed. My list length was only about 36k when I found the answer.

David Moore - 5 years, 6 months ago

Log in to reply

It was the value that is "big enough". Note, the product generates the powers of the prime factors. I do not doubt I am checking more things than I need to. It is a bonehead approach,but it works!

Thaddeus Abiy - 5 years, 6 months ago

Log in to reply

Ok thanks, it might even be more efficient than my method, since you only have to sort your list once. I initially tried solving the problem by just looking at the integer powers for the prime factorization, but I couldn't figure out an easily implementable rule to find the next fine number, given only the prime factorization of the preceding one.

I suspect it may be one of those sneakily hard problems that involves highly non-obvious properties about the recurrences of particular powers along the number-line, kind of like Fermat's last theorem.

David Moore - 5 years, 6 months ago
Maria Kozlowska
Aug 7, 2015

I do those things in SQL.

Here is an SQL statement in MS Access 

1
2
 
SELECT 2^[T].[no]\*3^[T_1].[no]*5^[T_2].[no]*7^[T_3].[no] AS Fine
FROM T, T AS T_1, T AS T_2, T AS T_3;

My table T contains integers from 0 0 to 28 28 . I sort the outcome and pick the 4001 4001 th element ( the first number is 1 and I exclude it from numbering).

3 Helpful 0 Interesting 0 Brilliant 0 Confused

This is cool. I have never seen an SQL solution to a brilliant problem before.

Thaddeus Abiy - 5 years, 10 months ago
Arulx Z
Aug 6, 2015 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
 
>>> def fine(n):
        for x in [2,3,5,7]:
            while n % x == 0:
                n /= x
        return n == 1

>>> n = 2
>>> count = 0

>>> while count != 4000:
       count += fine(n)
       n += 1

>>> print n

3 Helpful 0 Interesting 0 Brilliant 0 Confused

Moderator note:

Can you explain in words what the first section of your code is doing?

@Calvin Lin , here's what I'm doing in the first section -

Since brute forcing can be long and tedious, I found a better approach to check if only factors of a number are 2, 3, 5, 7.

I first check if any number n n is divisible 2. If it is, I divide it by 2 and I repeat this process again. Once the number is no more divisible by 2, I move on to 3. I essentially do the same thing with 3 and then continue to 5 and 7.

Once I've completed the process, I check if the n n is equal to 1. If it is, then it is a fine number. This is because if the number is fine, it's only prime factors are 2, 3, 5, 7. Hence when I divide away all of them, number must be equal to 1.

Arulx Z - 5 years, 10 months ago
Bill Bell
Jul 31, 2015

Producing this code involved making just a slight modification to one of those available at Rosetta code , which in turn is a translation of a Haskell code. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
## also known as 7-smooth numbers

from itertools import islice, chain, tee

def merge(r, s):
    rr = r.next()
    ss = s.next()
    while True:
        if rr < ss:
            yield rr
            rr = r.next()
        else:
            yield ss
            ss = s.next()

def p(n):
    def gen():
        x = n
        while True:
            yield x
            x *= n
    return gen()

def pp(n, s):
    def gen():
        for x in (merge(s, chain([n], (n * y for y in fb)))):
            yield x
    r, fb = tee(gen())
    return r

def humble(a, b = None):
    if not b:
        b = a + 1
    seq = (chain([1], pp(7,pp(5, pp(3, p(2))))))
    return list(islice(seq, a - 1, b - 1))

print humble(4001)[0]

2 Helpful 0 Interesting 0 Brilliant 0 Confused
Cheng Wei Chang
Jan 24, 2016

my solution in python using heap and set, not optimized 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
 
from heapq import *
candidates=[2,3,5,7]
candidateset=set(candidates)
finenums=[]
i=0
while len(finenums)<5000 and len(candidates)>0:
    x=heappop(candidates)
    i=i+1
    if i<20 or i==4000:print i,x
    finenums.append(x)
    for num in [2,3,5,7]:
        y=num*x
        if y not in candidateset:
            heappush(candidates,y)
            candidateset.add(y)

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...