Problem 179

[hk]

You count 93 because 93 and 93+1 have 4 divisors
You count 94 because 94 and 94+1 have 4 divisors
So these three count for 2 pairs and not 3 or 4.

[renosis]

Thanks! I got the answer!

[Oliver1978]

I'm a little lost with this.

Code: Select all

2, 3
14, 15
15, 16
21, 22
26, 27
33, 34
34, 35
38, 39
44, 45
57, 58
63, 64
75, 76
81, 82
85, 86
86, 87
93, 94
94, 95
98, 99

This is what I get for n < 100; exactly 18 elements. For n < 1000 I get 126. According to some previous post that number is way off. Could anybody confirm this?

[mpiotte]

I'm a little lost with this.

Code: Select all

...
15, 16
...

This is what I get for n < 100; exactly 18 elements. For n < 1000 I get 126. According to some previous post that number is way off. Could anybody confirm this?

15 has four divisors: 1, 3, 5, 15
16 has five divisors: 1, 2, 4, 8, 16
Some of your pairs are incorrect.

[Oliver1978]

I see ; back to the drafting board...

/* edit */

I've reworked my sample and now get 15 elements...

Code: Select all

    2, 3
    14, 15
    21, 22
    26, 27
    33, 34
    34, 35
    38, 39
    44, 45
    57, 58
    75, 76
    85, 86
    86, 87
    93, 94
    94, 95
    98, 99

That way it makes 118 elements for n < 1000.

/* edit - again */

That solved it. Thanks for the hint, mpiotte!

[crypto_rsa]

I've been thinking about this problem for quite a long time but I haven't been able to figure out any speedups. Is there a trick to skip some values? (I am not asking what kind of trick). It seems to me that no particular property of the factorizations of n and n + 1 can be derived without actually calculating them.

[angzhiping]

I've been thinking about this problem for quite a long time but I haven't been able to figure out any speedups. Is there a trick to skip some values? (I am not asking what kind of trick). It seems to me that no particular property of the factorizations of n and n + 1 can be derived without actually calculating them.

Doesn't seem to have any trick of skipping values. Generating all divisiors for integers up till n can be easily accomplished in O(n*log(n)) time, so it is reasonably efficient to work on every integer up to 10,000,000.

You can also push the time complexity down to O(n*log(log(n))) by avoiding explicitly enumerating all divisors. I'm afraid it is next to impossible to go faster than linear time.

[crypto_rsa]

Doesn't seem to have any trick of skipping values. Generating all divisiors for integers up till n can be easily accomplished in O(n*log(n)) time, so it is reasonably efficient to work on every integer up to 10,000,000.

You can also push the time complexity down to O(n*log(log(n))) by avoiding explicitly enumerating all divisors. I'm afraid it is next to impossible to go faster than linear time.

Well almost all my solutions to previous Euler problems take advantage of some "trick" which usually significantly cuts down the number of numbers to investigate, so I was expecting something similar here. And I usually get the result in less than a second. For problem 179 it seems I need to investigate all the numbers less than 10,000,000 and so far I haven't been able to do so in less than 40 seconds. I still think I must be missing something

[MHealy]

Well almost all my solutions to previous Euler problems take advantage of some "trick" which usually significantly cuts down the number of numbers to investigate, so I was expecting something similar here. And I usually get the result in less than a second. For problem 179 it seems I need to investigate all the numbers less than 10,000,000 and so far I haven't been able to do so in less than 40 seconds. I still think I must be missing something

I'm not particularly well-versed in complexity, so I'm not sure if I'm repeating what the above the poster has said. However, I think it is fair to say that there is a "trick" for this question which, although not cutting down the number of possible candidates, significantly reduces the run time in another way. I won't go into more detail as it would spoil the problem; it suffices to say that it's a fairly common method to solve such problems.

I just had a look at my own solution to this problem - it didn't take advantage of this, and hence, it took a very long time to run. I'm not sure how long (10 minutes, at least), but it was more than enough time for me to write two new solutions from scratch, based around the same "trick", each of which completes in well less than a second.

I think I am misreading the last part of your post, so: are you saying you can solve it, just in more than 40 seconds? Or that you are terminating your programs after 40 seconds, without the solution? If the former, perhaps check the private forum for this problem (they are always invaluable, and a significant reason why I can now solve this kind of problem much more efficiently).

[crypto_rsa]

I think I am misreading the last part of your post, so: are you saying you can solve it, just in more than 40 seconds? Or that you are terminating your programs after 40 seconds, without the solution? If the former, perhaps check the private forum for this problem (they are always invaluable, and a significant reason why I can now solve this kind of problem much more efficiently).

My solution actually terminates in 40 seconds. I suppose it gives the correct answer but I have not yet posted it precisely because I was trying to find a faster algorithm in the first place But I guess I will have to do it and then check the private forum to see what the "trick" is.

[angzhiping]

My solution actually terminates in 40 seconds. I suppose it gives the correct answer but I have not yet posted it precisely because I was trying to find a faster algorithm in the first place But I guess I will have to do it and then check the private forum to see what the "trick" is.

By using the O(n*log(n)) method of explicitly counting divisors for every integer up to 10^7-1, it takes 1.8 secs on C++. Don't think there is a need to use any special kind of secret computational sauce.

[crypto_rsa]

By using the O(n*log(n)) method of explicitly counting divisors for every integer up to 10^7-1, it takes 1.8 secs on C++. Don't think there is a need to use any special kind of secret computational sauce.

Yes, I've already learned that. I ran my code (enhanced with a cache, so that it actually runs in 5 seconds), posted the result and got into the problem forum where I - much to my dismay - learned that this problem indeed does not require any deeper mathematical insight and that the fastest algorithms which solve it are, frankly, quite naive. Fortunately, it's an exception rather than the rule among the problems I've solved so far.

[angzhiping]

I'm not particularly well-versed in complexity, so I'm not sure if I'm repeating what the above the poster has said. However, I think it is fair to say that there is a "trick" for this question which, although not cutting down the number of possible candidates, significantly reduces the run time in another way. I won't go into more detail as it would spoil the problem; it suffices to say that it's a fairly common method to solve such problems.

Is your technique sublinear?

[MHealy]

Is your technique sublinear?

My technique is almost identical to Georg's post on the first page of the private board (which it amazes me too as long as he says back in 2008 - it runs in about 500ms in my laptop from 2011). I'm afraid I don't know exactly what sublinear means in a programming context, but I'm fairly sure the answer is sadly not. The limit in this problem just happens to be low enough that it's very fast.

I ran my code (enhanced with a cache, so that it actually runs in 5 seconds), posted the result and got into the problem forum where I - much to my dismay - learned that this problem indeed does not require any deeper mathematical insight and that the fastest algorithms which solve it are, frankly, quite naive.

Sorry to hear this. I think the method used is interesting, if not interesting mathematically. I replied to your post in the private forum to address a particular issue you raised, though.

[crypto_rsa]

Sorry to hear this. I think the method used is interesting, if not interesting mathematically. I replied to your post in the private forum to address a particular issue you raised, though.

Thanks for your insightful and interesting post!

[angzhiping]

Is your technique sublinear?

I'm afraid I don't know exactly what sublinear means in a programming context, but I'm fairly sure the answer is sadly not. The limit in this problem just happens to be low enough that it's very fast.

An algorithm runs in sublinear time if it inspects a far smaller subset of the problem size. For example, binary search on a sorted array of $N$ elements inspects at most $\log_{2}(N)$ entries, and therefore runs in sublinear time.

[ashishn42]

I wrote this code based on Sieve of Eratosthenes,which gives the answer <snip>.The answer is not getting accepted though. Can someone please look into what I am doing wrong ?

This is the link to my code..

<snip>

EDIT: result and code removed by moderator

[Georg]

Line 44 is suspect.

[ashishn42]

But that line is simply cleaning up the contribution of previous prime powers and adding the new contribution.

[Georg]

Did you verify that your program ends with v[14] == 4?