Problem 047

[rpmuller]

I'm a little confused about Problem 47. The description states that the first three consecutive numbers with distinct prime factors are:

644 = 2^2 x 7 x 23
645 = 3 x 5 x 43
646 = 2 x 17 x 19.

How are these distinct, when

24 = 2^3 x 3
25 = 5^2
26 = 2 x 13

are not distinct? I'm probably missing something obvious, I realize.

[daniel.is.fischer]

You are missing one occurence of the word three. Given are the first three consecutive numbers with three distinct prime factors each.

[rpmuller]

You are missing one occurence of the word three. Given are the first three consecutive numbers with three distinct prime factors each.

Thanks. I realized it was something simple.

[sagi]

hi,
this may be a simple clarification and me being an idiot not being able to spot it ... here goes ..

what does the question mean when they say these numbers have 3 DISTINCT prime factors ..
644 = 2^2 * 7 * 23
645 = 3 * 5 * 43
646 = 2 *17 * 19.

because, 2 is repeated (prime factor) in 644 and 646 ( and so it will be in EVERY 2nd number, even numbers are all divisible by 2). .
and EVERY composite number has distinct prime factors ...

i m confused on this one...

[hk]

You should look at the numbers separatedly.
644 has one or more factors two, one or more factors seven and one or more factors 23.
So you need one ore more factors of three different primes to compose 644 multiplying one ore more of these three primefactors.
To put it into a formula:
A number n has three distinct primefactors if there exist 3 primes p1,p2,p3 so that n=(p1^a)*(p2^b)*(p3^c) with a,b and c≥1

[sagi]

thanks! .. solved the problem .. code time approx 5 minutes ( stupid me )

[Reinderien]

http://projecteuler.net/index.php?secti ... lems&id=47 seems ambiguous to me.

Does a number qualify if it has exactly four prime factors, or 'at least' four prime factors? Also, without looking at the second example, one wouldn't know if the question asked for uniqueness among the factors of one number or the factors of all four numbers. (It's the former case because of the recurring 2.)

[hk]

Examples are integral part of the problem description, so that settles one of the "ambiguities"
Moreover, without examples, mathematical reasoning will show that 4 consecutive numbers will always have a common factor 2.
The second question "exactly four" or "at least four" will be settled by solving the problem, i.e. solve it first using "at least". Then decide whether there is an ambiguity or not by checking the number of distinct primefactors of the first solution that pops up doing so.

[laune]

The wording of problem 47 is confusing. By definition, a "prime factor" is a prime number, but after some consideration it becomes obvious that the solution counts distinct "powers of prime factors". (I'm not a native speaker, so it's possible that I'm missing something, but the definition in wikipedia seems to support my view.)

[karlo]

A prime factor is a prime that divides the number. For example both 6=2*3 and 12=2^2*3 have 2 prime factors, 2 and 3.

[laune]

Exactly. But look at problem 47, where 2² is counted as a "prime factor" different from 2.

[Robert_Gerbicz]

Exactly. But look at problem 47, where 2² is counted as a "prime factor" different from 2.

See: in that example: 644 = 2² × 7 × 23
We say here that it has got three different prime factors: 2,7,23.

In number theory there is also a function for this: omega(n)=number of different prime factors of n.

[laune]

OK, "different" sounds better that "distinct" (at least to me). In other words, the cardinality of the set of prime factors must be 3 (or whatever). - thanks!

[daniel.is.fischer]

"different" and "distinct" mean the same. Pity the one you weren't familar with was chosen

[mdean]

The second question "exactly four" or "at least four" will be settled by solving the problem, i.e. solve it first using "at least". Then decide whether there is an ambiguity or not by checking the number of distinct primefactors of the first solution that pops up doing so.

Isn't it easier for an administrator to insert the words "at least" or "exactly" than it is for us to code for 2 different solutions? I mean even if the answers to both possibilities are the same (and I have not done the problem yet, so I don't know if this is the case), an ambiguity in the question still exists.

[hk]

The second question "exactly four" or "at least four" will be settled by solving the problem, i.e. solve it first using "at least". Then decide whether there is an ambiguity or not by checking the number of distinct primefactors of the first solution that pops up doing so.

Isn't it easier for an administrator to insert the words "at least" or "exactly" than it is for us to code for 2 different solutions? I mean even if the answers to both possibilities are the same (and I have not done the problem yet, so I don't know if this is the case), an ambiguity in the question still exists.

Or you code a solution that checks both options simultaneously.

[ymersvennson]

(Quoted beneath)

I think this can be understood as both n distinct prime factors (within itself), or n distinct prime factors (within itself and the others).

For instance, if we take the numbers 18 (2*9) and 22 (2*11).
They both have two distinct prime numbers within themselves. But they don't have 2 distinct prime factors within themselves and the other. Eg, 22 has the prime factor 2 which is in 18, so it is not distinct.

I misunderstood the problem in this way, and that makes it much more difficult.


"""
The first two consecutive numbers to have two distinct prime factors are:

14 = 2 7
15 = 3 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² 7 23
645 = 3 5 43
646 = 2 17 19.

Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?
"""

[ymersvennson]

Luckily for me, the answer to this harder problem is actually the same. ( Unless I made an error somewhere.)

[euler]

(Please don't start a new topic. I've moved your posts to the thread that already existed for Problem 047.)

Did you notice the word, consecutive?

[thundre]

I think this can be understood as both n distinct prime factors (within itself), or n distinct prime factors (within itself and the others).

For instance, if we take the numbers 18 (2*9) and 22 (2*11).
They both have two distinct prime numbers within themselves. But they don't have 2 distinct prime factors within themselves and the other. Eg, 22 has the prime factor 2 which is in 18, so it is not distinct.

I misunderstood the problem in this way, and that makes it much more difficult.

2 consecutive numbers cannot be multiples of any of the same primes.

Any group of 4 consecutive numbers must contain two numbers which are multiples of 2. (In fact, the 3-number example given in the problem does.)

So if any reader makes this error, he should be able to correct himself, as you did.