Project Euler

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Project Euler

Postby Xanthir » Tue Sep 30, 2008 11:56 pm UTC

CormanLisp 3.0.

The memoized version wasn't dying, but it would error out with a "Cant' grow hashtable" error when it hit 1.5M/3M entries (attempting to grow it to 6M entries).

My completely iterative, bruteforce, non-memoized version is the one dying:

Code: Select all

(loop for x from 1 to 999999
      with long-chain-steps = 0
      with long-chain-num = 1
      for steps = (collatz x)
      if (> steps long-chain-steps)
        do (setf long-chain-steps steps long-chain-num x)
      finally (return (list long-chain-steps long-chain-num)))
(defun collatz (n)
  (loop for x = n then (if (evenp x) (/ x 2) (1+ (* 3 x)))
        for steps upfrom 1
        until (= x 1)
        finally (return steps)))

I have no clue why. Like I said, I was able to find the answer by just running it with small enough increments (100k works for most increments, with 50k for the few that still die), but the problem is very annoying. There's not even any consing! I'll probably take it the Corman forums and ask if they know anything.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Qoppa
Posts: 694
Joined: Sat Nov 24, 2007 9:32 pm UTC
Location: Yes.

Re: Project Euler

Postby Qoppa » Wed Oct 01, 2008 12:34 am UTC

I hadn't heard of memoizing before reading this thread. After a quick trip to wikipedia, I must say this looks like it could be very, very handy for some of the problems. Thank you for the idea.

Code: Select all

_=0,w=-1,(*t)(int,int);a()??<char*p="[gd\
~/d~/\\b\x7F\177l*~/~djal{x}h!\005h";(++w
<033)?(putchar((*t)(w??(p:>,w?_:0XD)),a()
):0;%>O(x,l)??<_='['/7;{return!(x%(_-11))
?x??'l:x^(1+ ++l);}??>main(){t=&O;w=a();}

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Wed Oct 01, 2008 4:00 am UTC

Qoppa wrote:I hadn't heard of memoizing before reading this thread. After a quick trip to wikipedia, I must say this looks like it could be very, very handy for some of the problems. Thank you for the idea.

This is what it's all about, spreading ideas, concepts and knowledge.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Project Euler

Postby Xanthir » Wed Oct 01, 2008 1:25 pm UTC

Memoizing is a poor man's dynamic programming.

Edit: And I mean nothing but good by this statement.

For an example of how ridiculously easy it is to memoize in a decent language, check this out. Here's a form of the collatz function suitable for memoization:

Code: Select all

(defun collatz (n)
    (if (= n 1)
        1
        (1+ (if (evenp n)
            (collatz (/ n 2))
            (collatz (1+ (* n 3)))))))

Here's the function after applying memoization:

Code: Select all

(defmemoized collatz (n)
    (if (= n 1)
        1
        (1+ (if (evenp n)
            (collatz (/ n 2))
            (collatz (1+ (* n 3)))))))

^_^ Of course, that requires an appropriate framework underneath it:

Code: Select all

(defun memoize (fn)
  (let ((cache (make-hash-table :test #'equal)))
    (lambda (&rest args)
      (multiple-value-bind (val win)
          (gethash args cache)
        (if win val (setf (gethash args cache) (apply fn args)))))))
(defmacro defmemoized (sym lambda-list &body b)
  `(flet ((fn ,lambda-list ,@b))
     (let ((mfn (memoize #'fn)))
       (defun ,sym (&rest x) (apply mfn x)))))

You don't even have to understand the tools, though, to use memoization. Just change your function definition, and you're done. Alternately, you can just call memoize directly to decorate your already-defined function, in the way that Python decorates functions. (This is what the defmemoized macro does for you, except it then binds the function to a given symbol in the global space.)

The method is obviously a bit more difficult in languages that don't support true macros or at least lambdas as a first-class type, but the basic idea is the same. Pass a hash table with the function and, with every call, first check the hash to see if the function has been called with those arguments before. If so, return the stored answer. If not, compute the function, then store the answer.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Guff
Posts: 165
Joined: Thu Jan 03, 2008 11:56 pm UTC

Re: Project Euler

Postby Guff » Wed Oct 01, 2008 11:27 pm UTC

qbg wrote:
Guff wrote:And I want to figure out how to tackle problem 188. I'm not well acquainted with bignum arithmetic, and obviously evaluating [imath]1777\uparrow\uparrow1855[/imath] would not be practical.

Sounds useful:
Spoiler:
Modular exponentiation?

Yeah, I figured that was relevant, but didn't understand it. And I still don't, but I managed nonetheless to solve the problem.
Spoiler:
I just incorporated taking the remainder into each step of my tetration function. Finished in about 40ms. :)

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Project Euler

Postby Xanthir » Thu Oct 02, 2008 12:01 am UTC

I'll explain it real quick-like.

Modular exponentiation is based on the fact that (m2) mod n is equivalent to (m mod n)2 mod n. Why is this? Simply to see.

First, let's rewrite m in terms of n, so that we get m = (a*n+b), where 0 <= b < n. That is, m is some multiple of n, plus a bit more (this "bit more" may be 0 if m is an exact multiple of n). Now do some math!

(a*n+b)2 mod n = (a2*n2 + 2*a*b*n + b2) mod n. We can distribute mod over addition, so this is equal to (a2*n2 mod n) + (2*a*b*n mod n) + (b2 mod n). The first two terms are multiples of n, and so are equal to 0 mod n. We're left with b2 mod n.

Now let's do the same thing to the other side, (m mod n)2 mod n. We get ((a*n + b) mod n)2 mod n = ((a*n mod n) + (b mod n))2 mod n = (0 + (b mod n))2 mod n. Now, we previously *defined* b as being 0 <= b < n, so (b mod n) is simply b. Thus, the final reduction takes us to b2 mod n, which is the same as the other form.

Thus, the two forms are equivalent, and you can always mod a number before exponentiating-and-then-modding it without changing the answer.

Edit: Finished, and corrected a stupid mistake. I knew something was going wrong when I had to cut my post off, but it wasn't until I was walking to my car that I realized what it was.
Last edited by Xanthir on Thu Oct 02, 2008 1:33 pm UTC, edited 1 time in total.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Guff
Posts: 165
Joined: Thu Jan 03, 2008 11:56 pm UTC

Re: Project Euler

Postby Guff » Thu Oct 02, 2008 1:57 am UTC

Hmm, that's pretty interesting. I've been trying to learn more about number theory, but all I've got is a 200-page paperback that focuses primarily on a combinatorial approach. I also have little knowledge of combinatorics. :(

Also, from reading the thread on PE, it would seem that my solution, which was similar to many of the others, was only accidentally correct for this particular example. I dunno, I'll have to look into it more after I think about it some more. And solve some more problems.

User avatar
tetsujin
Posts: 426
Joined: Thu Nov 15, 2007 8:34 pm UTC
Location: Massachusetts
Contact:

Re: Project Euler

Postby tetsujin » Thu Oct 02, 2008 3:13 pm UTC

Here's the bit that confused me about that problem...

I read up on modular exponentiation, and so knew that (a*b)mod n = ((a mod n) * (b mod n)) mod n, ab mod n = (a mod n)b, etc...

But I didn't find anything that says that ab mod n = (a mod n)(b mod n) mod n. My final solution did depend on this property, but I don't know why it's true. Without this property, in order to calculate (a^^b) mod n, you would first have to calculate (a^^(b-1)) in order to calculate (a^^b) mod n = (aa^^(b-1)) mod n = (a mod n)a^^(b-1) mod n... In other words, without that property you can't carry the "mod" into your recursive computation step...
---GEC
I want to create a truly new command-line shell for Unix.
Anybody want to place bets on whether I ever get any code written?

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Project Euler

Postby jaap » Thu Oct 02, 2008 3:56 pm UTC

tetsujin wrote:But I didn't find anything that says that ab mod n = (a mod n)(b mod n) mod n. My final solution did depend on this property, but I don't know why it's true.


That's because it isn't true.
26 mod 5 = 64 mod 5 = 4
26%5 = 21 = 2

For a prime p, ap = a = a1 mod p. This is Fermat's Little Theorem. Therefore if you are working modulo a prime p, you can reduce any exponent by a multiple of p-1.

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Project Euler

Postby Xanthir » Thu Oct 02, 2008 4:01 pm UTC

It's, erm, *not* generally true. Take 77 mod 5. This equals 3. We also know that 27 mod 5 = 3, because of the rules of modular exponentiation. However, 22 mod 5 = 4, which shows that you can't move the mod into the exponent in general.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
tetsujin
Posts: 426
Joined: Thu Nov 15, 2007 8:34 pm UTC
Location: Massachusetts
Contact:

Re: Project Euler

Postby tetsujin » Thu Oct 02, 2008 4:04 pm UTC

Xanthir wrote:It's, erm, *not* generally true. Take 77 mod 5. This equals 3. We also know that 27 mod 5 = 3, because of the rules of modular exponentiation. However, 22 mod 5 = 4, which shows that you can't move the mod into the exponent in general.


Yeah, previous post covered that. So I solved the thing but I still don't understand why my solution works. The modulus (10^8) is not a prime... So how does modular exponentiation help you get to 1777^^1855?

I guess I'll read the problem 188 forum, see if that enlightens me...
(EDIT): post 8 in the problem 188 forum, by logopetria, was very enlightening... Had I attacked problem 188 after problem 26, instead of before it, I might have seen this property...
---GEC
I want to create a truly new command-line shell for Unix.
Anybody want to place bets on whether I ever get any code written?

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Project Euler

Postby Xanthir » Thu Oct 02, 2008 4:50 pm UTC

Sorry, didn't pay attention to the notice that someone had posted while I was composing.

Man, I don't even know how to approach #26. I *know* there's some property that Euler probably discovered that would help me here, I just don't know it.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
tetsujin
Posts: 426
Joined: Thu Nov 15, 2007 8:34 pm UTC
Location: Massachusetts
Contact:

Re: Project Euler

Postby tetsujin » Thu Oct 02, 2008 5:06 pm UTC

Xanthir wrote:Sorry, didn't pay attention to the notice that someone had posted while I was composing.


No sweat, I was just already feeling a little foolish after the first time somebody pointed out my solution (already suspect, despite having generated the right answer) was wrong. :)

Man, I don't even know how to approach #26. I *know* there's some property that Euler probably discovered that would help me here, I just don't know it.


Well, the things I immediately noticed in #26 was that factors of 2 and 5 contribute nothing to loops, since they get cancelled out over a few decimal digits. So I figured the solution would be some largish number, probably a prime or the product of a few primes with no factors of 2 or 5. But not being entirely sure of this, I solved it by searching the problem space.

The key property, I guess, is that any rational number has either a finite decimal representation, or a finite number of decimal digits followed by an infinite loop of a finite number of digits... In other words, you know your seach for a loop can always terminate - either you'll come up with a perfect decimal representation of the rational number (no loop) or you'll find a loop of finite length.

The basic process of finding the length of the loop is pretty straightforward. My first thought was to actually generate that sequence, performing a long division-ish algorithm to generate each digit in the sequence - and possibly skipping some number of digits at the start of the sequence to allow the sequence to settle into its loop. Then it's just a matter of testing. "Is this digit the start of a loop of size 1? size 2? size 3?" etc...

Of course, once I wrote it all out I realized you don't even have to follow the whole sequence of the loop to detect a loop. At each stage in the process of generating the digit sequence, there is a state that the division process is in... Any time you reach that state, you know the sequence of digits generated from that point on will be the same. Hence, any time you hit a state you've already seen, you've found a loop.
---GEC
I want to create a truly new command-line shell for Unix.
Anybody want to place bets on whether I ever get any code written?

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Project Euler

Postby Xanthir » Thu Oct 02, 2008 7:45 pm UTC

See, that's approximately what I thought about doing originally, but I set it aside to see if I could find anything clever and didn't follow those original thoughts through to a useful conclusion. I suppose I'll just have to invoke manual long division then.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Baxter
Posts: 46
Joined: Sun Oct 12, 2008 3:30 am UTC

Re: Project Euler

Postby Baxter » Wed Oct 15, 2008 12:37 pm UTC

Slightly off topic perhaps but after doing problem http://projecteuler.net/index.php?secti ... lems&id=11 I was reminded of a similar site, it seemed to be more focused on brevity in the actual source code, the only problem I recall from it was that you had to walk a twisting path of chars to transform them into a single string it looked a little like this:

Code: Select all

A
B
C    NOP
D    M QRSTUV
E  JKL      W
FGHI      ZYX


The result in this case would be the alphabet it's alphabetical order.

I think you may have had to upload source-code to an on-line interpreter as it has a league table of ways to solve each problem in the fewest characters for each language it was attempted in.
Cars Cutters and Cadavers

Dongorath
Posts: 93
Joined: Tue Oct 16, 2007 1:17 pm UTC

Re: Project Euler

Postby Dongorath » Wed Oct 15, 2008 1:17 pm UTC

Anarchy golf has a context has to the shortest program to resolve certain problems. Yours looks vaguely like Show the way.

User avatar
Baxter
Posts: 46
Joined: Sun Oct 12, 2008 3:30 am UTC

Re: Project Euler

Postby Baxter » Thu Oct 16, 2008 1:16 am UTC

Yes that does look about right, I think my version is more fun however.

I've been browsing around PE and liked the look of: http://projecteuler.net/index.php?secti ... ems&id=208

It seems so simple until you realise what a massive number of possibilities there are, and that regular pentagons don't tessellate (on a euclidean plane). has anyone thought about this one at all?

I assume that it can't be solved with a search tree because by the time there are any definite indications of failure (that I can think of) you're up in the ~2^30 branches region.

Dongorath
Posts: 93
Joined: Tue Oct 16, 2007 1:17 pm UTC

Re: Project Euler

Postby Dongorath » Thu Oct 16, 2008 8:37 am UTC

Nope, didn't think about, seems a bit too complex for my little head... But it's a binary tree of depth 70. A path can be represented by an array of 70 bits (clockwise or anticlockwise choice). Symetry should help a bit (if you have a path p, its bitwise "not" should be a valid solution too). If you have a mean to check your distance from your starting point and the maximum you can travel with the remaining moves, you might be able to prune your tree starting at half the tree. But I'm sure one should find the way to check if there exists a path between two points with a finite or limited number or arcs knowing the current bearing... But just a wild guess...

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Project Euler

Postby jaap » Thu Oct 16, 2008 8:56 am UTC

Dongorath wrote:But it's a binary tree of depth 70. A path can be represented by an array of 70 bits (clockwise or anticlockwise choice).


Better would be to go to depth 30, and then count how many pairs of such paths fit together at their ends to form a loop back to the starting position.

Still, searching a binary tree of depth 30 is still too much, and there is a much better way to do this....
... but I'm not telling.

Dongorath
Posts: 93
Joined: Tue Oct 16, 2007 1:17 pm UTC

Re: Project Euler

Postby Dongorath » Thu Oct 16, 2008 9:38 am UTC

Well, I'm sure it's one of those problem where you actually build the good solutions and count them instead of checking all the possibilities. I'm sure the symetry "trick" still apply (you only have to build half the possibilities). Good luck to those willing to try this one :mrgreen:

User avatar
Baxter
Posts: 46
Joined: Sun Oct 12, 2008 3:30 am UTC

Re: Project Euler

Postby Baxter » Thu Oct 16, 2008 1:46 pm UTC

Dongorath wrote:Well, I'm sure it's one of those problem where you actually build the good solutions and count them instead of checking all the possibilities. I'm sure the symetry "trick" still apply (you only have to build half the possibilities). Good luck to those willing to try this one :mrgreen:


You little beauty! I've got a little logo-clone (visual thinking always helps) working and I'm working though some of the smaller cycles now. as a side note would anyone have any ideas on how to transform the Cartesian jumble of paths into a Poincaré disk representation?

User avatar
spdqbr
Posts: 171
Joined: Sat Mar 08, 2008 1:41 am UTC
Location: A shaker of salt

Re: Project Euler

Postby spdqbr » Sat Oct 18, 2008 7:38 am UTC

Number 90's been knocking me around for a bit. This is currently incorrect (and ugly) in java:

Code: Select all

//I have removed the code as the error is now fixed.


I'm stumped, I think it should give the correct solution, but it's not. Any tips (just a nudge please).
Last edited by spdqbr on Sun Oct 19, 2008 4:08 pm UTC, edited 1 time in total.
In questions of science, the authority of a thousand is not worth the humble reasoning of a single individual.

Galileo

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Project Euler

Postby Xanthir » Sat Oct 18, 2008 2:39 pm UTC

Not entirely sure, but it looks like your targets are off. I can't entirely decipher your moonspeak, so you may have a correction embedded somewhere in there, but (frex) one of your targets is {0,9}. This can *also* be satisfied by {0,6}, though. Similar, {1,6} can also be satisfied by {1,9}.

Is there any way to specify a target as an OR of multiple individual targets? If so, try that out. If not, convert all the 9s into 6s and only choose from {0-8}. This way you'll be sure not to miss anything, but some of the targets will be folded into other targets. Correcting to account for this should be relatively trivial.

I'm a touch confused by the problem, though. Are you supposed to be counting distinct extended sets?
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
spdqbr
Posts: 171
Joined: Sat Mar 08, 2008 1:41 am UTC
Location: A shaker of salt

Re: Project Euler

Postby spdqbr » Sat Oct 18, 2008 4:12 pm UTC

The 6 - 9 replacement is taken care of during the extraction of cube arrangement from the arraylist, if it has a six but not a nine, it adds a nine and vice verse. I hadn't thought that it might be counting distinct extended sets instead of just distinct sets, so I'll give that a shot.
In questions of science, the authority of a thousand is not worth the humble reasoning of a single individual.

Galileo

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Project Euler

Postby Xanthir » Sun Oct 19, 2008 2:43 pm UTC

Hmm, though. I don't think that's right. An arrangement with a six and an arrangement with a 9 are *functionally* the same, but they are distinct in the counting. Just adding a six or a nine effectively hides several arrangements.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
spdqbr
Posts: 171
Joined: Sat Mar 08, 2008 1:41 am UTC
Location: A shaker of salt

Re: Project Euler

Postby spdqbr » Sun Oct 19, 2008 4:06 pm UTC

The underlying theory was correct but there was a functional oversight involving me extending the 6's and 9's by just appending them, and then using binary search to test for digits of squares. Added 2 lines to the code and got the correct answer. FYI It is distinct sets, not distinct extended sets they're after.

In the spirit of the competition I will remove the code above.
In questions of science, the authority of a thousand is not worth the humble reasoning of a single individual.

Galileo

User avatar
The Hyphenator
Posts: 791
Joined: Mon Nov 19, 2007 2:16 am UTC
Location: The Shades, Ankh-Morpork

Re: Project Euler

Postby The Hyphenator » Sun Oct 19, 2008 4:24 pm UTC

I've been working on a solution to #198 for a long, long time, and think I've got the answer. But it's not right.

My program basically rests on the assumption that all ambiguous numbers' best approximations can be represented as fractions with the same numerator, and denominators that differ by one (eg. 1/100 and 1/101), and that all fraction pairs that follow this rule produce an ambiguous number. I haven't proven this, and have absolutely no idea how to, but it seems to be right for all the examples I tested (and the one on the site).

So... all I need to know is... is this assumption right?

I'm probably missing something really obvious and simple here...
The image link changes whenever I find a new cool website.
Spoiler:
Image

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Project Euler

Postby Xanthir » Mon Oct 20, 2008 1:00 am UTC

The Hyphenator wrote:I've been working on a solution to #198 for a long, long time, and think I've got the answer. But it's not right.

My program basically rests on the assumption that all ambiguous numbers' best approximations can be represented as fractions with the same numerator, and denominators that differ by one (eg. 1/100 and 1/101), and that all fraction pairs that follow this rule produce an ambiguous number. I haven't proven this, and have absolutely no idea how to, but it seems to be right for all the examples I tested (and the one on the site).

So... all I need to know is... is this assumption right?

I'm probably missing something really obvious and simple here...


Lessee... Okay, it's evident that all ambiguous numbers have BAs with denominators which differ by one. If a number r has two BAs of the form x/y and x/(y+2), then x/(y+1) will be between them, and thus will be closer to p than one of the assumed BAs, which produces a contradiction. It is not evident that the numerators must be the same. If you have a number r with BAs x/y and (x+1)/(y+1) (keep in mind that the latter is guaranteed to be larger), then there is no way to change the numerators to get closer, and it's possible that to make a number between the two (and thus a better approximation) would require a denominator beyond the allowed bounds. For example, if your denominator bound is 4, then the numbers 1/2 and 2/3 are best approximations for the number 7/12. 3/5 would be closer, but it's beyond the allowed bounds.

It *does* seem to be true, though, that for any two numbers x/y and x/(y+1), there is a number r for which they are both best approximations for some bound. Namely, take y+1 as the denominator bound. Similarly, any two numbers x/y and (x+1)/(y+1) (such that x != y) are BAs for some ambiguous number for some bound (again, take y+1 as the bound to guarantee it).

The goal then seem to just be to find all such pairs such that the resulting ambiguous number is both between 0 and 1/100, and such that the ambiguous number's denominator doesn't exceed 108. All ambiguous numbers have a very specific structure, so it should be relatively simple to count them.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
The Hyphenator
Posts: 791
Joined: Mon Nov 19, 2007 2:16 am UTC
Location: The Shades, Ankh-Morpork

Re: Project Euler

Postby The Hyphenator » Tue Oct 21, 2008 12:26 am UTC

Xanthir wrote:
The Hyphenator wrote:I've been working on a solution to #198 for a long, long time, and think I've got the answer. But it's not right.

My program basically rests on the assumption that all ambiguous numbers' best approximations can be represented as fractions with the same numerator, and denominators that differ by one (eg. 1/100 and 1/101), and that all fraction pairs that follow this rule produce an ambiguous number. I haven't proven this, and have absolutely no idea how to, but it seems to be right for all the examples I tested (and the one on the site).

So... all I need to know is... is this assumption right?

I'm probably missing something really obvious and simple here...
Lessee... Okay, it's evident that all ambiguous numbers have BAs with denominators which differ by one. If a number r has two BAs of the form x/y and x/(y+2), then x/(y+1) will be between them, and thus will be closer to p than one of the assumed BAs, which produces a contradiction. It is not evident that the numerators must be the same. If you have a number r with BAs x/y and (x+1)/(y+1) (keep in mind that the latter is guaranteed to be larger), then there is no way to change the numerators to get closer, and it's possible that to make a number between the two (and thus a better approximation) would require a denominator beyond the allowed bounds. For example, if your denominator bound is 4, then the numbers 1/2 and 2/3 are best approximations for the number 7/12. 3/5 would be closer, but it's beyond the allowed bounds.

It *does* seem to be true, though, that for any two numbers x/y and x/(y+1), there is a number r for which they are both best approximations for some bound. Namely, take y+1 as the denominator bound. Similarly, any two numbers x/y and (x+1)/(y+1) (such that x != y) are BAs for some ambiguous number for some bound (again, take y+1 as the bound to guarantee it).

The goal then seem to just be to find all such pairs such that the resulting ambiguous number is both between 0 and 1/100, and such that the ambiguous number's denominator doesn't exceed 108. All ambiguous numbers have a very specific structure, so it should be relatively simple to count them.
Ah, thanks, that makes sense. Now to code it...

((Also, did you really see the 2nd iteration of your sig first? I've only seen people with 17 or higher. :shock: ))
The image link changes whenever I find a new cool website.
Spoiler:
Image

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Project Euler

Postby Xanthir » Tue Oct 21, 2008 2:11 am UTC

The Hyphenator wrote:((Also, did you really see the 2nd iteration of your sig first? I've only seen people with 17 or higher. :shock: ))

Yup. Or at least, the first time I saw this sig it was from someone who *claimed* to have seen the 1st iteration. I had just happened to peek into News & Events one day (not a forum I regularly check), when I saw someone with Gen2. I can't remember who it was precisely, but it was a regular poster round these parts ("these parts" being Math, Science, Coding, or Comp Sci). My instinct is to say Gelsamel, but that can't be right unless he's recently changed his sig.

I didn't see all the Gen17's show up until about a week later, I think. It was several weeks after that that I finally broke down and added the line to my own sig. Unfortunately, it roughly corresponds to when I started seeing people knowingly perverting the system with Gen -3+i and stuff.

Note, though, that I browse at work with a custom stylesheet that hides signatures, so people may have been floating around with the things for a long time without me seeing them. It's only here at home (on Chrome, where user stylesheets aren't yet supported) that I see people's signatures (or avatars, or many other things. I'm very much a fan of minimalism, especially when it help to hide what I'm doing from casual onlookers.)

Edit: Crap, what I worked out above is incomplete. I left out the case of BAs x/y and (x+1)/y, with bound y. These produce an ambiguous number. Frex, 1/4 and 2/4 are BAs for the ambiguous number 3/8.

So, an ambiguous number is produced by the numerators differing by 1, the denominators differing by 1, or both. I've already established that having the numerators or denominator differing by more than 1 does *not* produce a pair of numbers which are BAs for some ambiguous number, and clearly having numerator and denominator both equal doesn't work either (as the "two" numbers are just 1, and are an exact approximation). That truly does cover every case, then.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
DrProfessorPhD
Posts: 55
Joined: Sat Oct 11, 2008 5:35 pm UTC

Re: Project Euler

Postby DrProfessorPhD » Wed Oct 29, 2008 9:56 pm UTC

I am completely stuck on (no laughing) number 3 for Python. My kludgy code is acting in ways I do not like. It can't xrange(600851475143) because it doesn't let it convert from a long int to an int. Yet, it acts buggy for other vaules. It spits out UnboundLocalError: local variable 'answer' referenced before assignment if I try 5, and gives me 500 as a result for 1000. Last I checked, 500 was not prime...

Warning, I am still very new so my code is probably very lacking in... skill.

Spoiler:

Code: Select all

def pf(number):
   for divisor in xrange(1, number):   #Go through and check 1 by 1
      if number % divisor == 0: #check for factorness
         for divisorfactor in xrange(2, divisor): #Go through divisorfactor
            if divisor % divisorfactor == 0: # check if the divisor is prime
               answer = divisor
   print answer #Since it will loop through and only record the last value, nothing else is needed


Can anyone give some non-spoilery hints for solving it?
I am probably a swordfighting octopus. In case you can't tell.

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Project Euler

Postby Xanthir » Wed Oct 29, 2008 11:53 pm UTC

The error thrown when you enter 5 will occur *anytime* you enter a prime. The *only* number that will divide 5 is 1, but xrange(2,1) will be empty, so you never get to set answer even once.

The wrong answer given when you enter 500 will happen with any other number. It'll always return the largest non-prime factor. This is because your inner loop sets answer=divisor specifically is divisor is *not* prime (it tests if divisor is divisible by another integer). Even if you fix this, it'll then still always return the largest divisor (not largest prime divisor), because it sets answer = divisor if *any* number *doesn't* divide divisor. What you need to do is set a flag to true before entering the inner loop, set it to false if you find a divisor of divisor, then set answer=divisor only if flag is still true *after* the loop.

These aren't spoiler-y, because you still have an *extremely* inefficient algorithm. There's a fun, easy simplification you can do (not the "square root of the number" thing) that will *drastically* reduce how many numbers you have to test through.

Also, go ahead and make a prime predicate. You'll need it, and it would greatly simplify your current code. You wouldn't need the flag variable explicitly, frex.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
DrProfessorPhD
Posts: 55
Joined: Sat Oct 11, 2008 5:35 pm UTC

Re: Project Euler

Postby DrProfessorPhD » Thu Oct 30, 2008 2:50 am UTC

Prime predicate? No idea what that means. Nor do I have any idea how to simplify a set like that.
I am probably a swordfighting octopus. In case you can't tell.

qbg
Posts: 586
Joined: Tue Dec 18, 2007 3:37 pm UTC

Re: Project Euler

Postby qbg » Thu Oct 30, 2008 3:39 am UTC

DrProfessorPhD wrote:Prime predicate? No idea what that means.

A predicate is a function that either returns true or false, so a prime predicate would be a function that returns true if its input is a prime number.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Thu Oct 30, 2008 9:34 am UTC

I just realized I've got most of the solution to that one in my current signature...
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

Dongorath
Posts: 93
Joined: Tue Oct 16, 2007 1:17 pm UTC

Re: Project Euler

Postby Dongorath » Thu Oct 30, 2008 12:52 pm UTC

If interpreted correctly, the following hint gives you the solution... Or at least the one I used...
Spoiler:
pf(84) == pf(42) == pf(21) == pf(7)

User avatar
DrProfessorPhD
Posts: 55
Joined: Sat Oct 11, 2008 5:35 pm UTC

Re: Project Euler

Postby DrProfessorPhD » Thu Oct 30, 2008 9:14 pm UTC

I tried thinking about it for a while, and either through sleepiness or sheer ineptitude, I can not figure out how to go about making a prime predicate.
I am probably a swordfighting octopus. In case you can't tell.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Project Euler

Postby Berengal » Thu Oct 30, 2008 9:39 pm UTC

Primes can only be divided by 1 or itself, right? So try dividing it by every other number. Of course, there are better ways...

You might want to create a list of primes and see if the candidate number is part of that list. Of course, with such a list, you wouldn't even need a prime predicate if you fetch your possible divisors from that list.
The predicate function could be used to generate such a list though. If a number isn't in the list of primes, and can't be divided by any numbers in the list, then it is obviously a prime number and should be added to the list. There are a few other restrictions to the tested number and the list it's tested against to make sure it's actually prime, and another restriction about which prime numbers can be added to the list to make sure it doesn't break on further iterations, but I'll leave them to you to figure out.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Project Euler

Postby Xanthir » Thu Oct 30, 2008 10:52 pm UTC

Dongorath wrote:If interpreted correctly, the following hint gives you the solution... Or at least the one I used...
Spoiler:
pf(84) == pf(42) == pf(21) == pf(7)

That highlights essentially the algorithm I used.

DrProfessorPhD wrote:I tried thinking about it for a while, and either through sleepiness or sheer ineptitude, I can not figure out how to go about making a prime predicate.

You're gonna have some problems with Project Euler if you can't figure out the numerical properties of primes and make a function out of it.

Another way to put this is, how did you expect your current function to work if you don't know how to tell that a number is prime?

Berengal hit it, though. The dumb-kludge way is to just mod it by every number from 2 to n-1. If any of them = 0, you know you don't have a prime. Again, this isn't a spoiler, because you already have the proper idea in your code, it's just that your implementation of it is broken.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
DrProfessorPhD
Posts: 55
Joined: Sat Oct 11, 2008 5:35 pm UTC

Re: Project Euler

Postby DrProfessorPhD » Fri Oct 31, 2008 2:12 am UTC

I'm going with the 'I should not talk to other people or think and then give up while sick and tired' excuse. I actually knew that property, I just wasn't thinking that way. I think I can get it now. Thanks for the help guys.
I am probably a swordfighting octopus. In case you can't tell.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 7 guests