Project Euler...

Everything else that doesn't fall into one of the other PB categories.
Post Reply
User avatar
Demivec
Addict
Addict
Posts: 4260
Joined: Mon Jul 25, 2005 3:51 pm
Location: Utah, USA

Post by Demivec »

I need a little help with #90. I formulated a solution but it doesn't seem to produce the correct result.

I produced cubes with the needed digits. Then I add in unneeded digits to fill in open places on a cube. I then count the unique cube arrangements. (if a cube has a 6 or 9 I know they are equivalent but different :wink: )

I come up with 38 different arrangements.
Top
User avatar
Michael Vogel
Addict
Addict
Posts: 2797
Joined: Thu Feb 09, 2006 11:27 pm
Contact:
Contact Michael Vogel

Post by Michael Vogel »

Demivec wrote:I need a little help with #90. I formulated a solution but it doesn't seem to produce the correct result.

I produced cubes with the needed digits. Then I add in unneeded digits to fill in open places on a cube. I then count the unique cube arrangements. (if a cube has a 6 or 9 I know they are equivalent but different :wink: )

I come up with 38 different arrangements.
Ui, it's just some weeks ago and I've already problems to understand my own solution :cry:

First of all, be careful: there are much (!) more possibilities, here is just a small part of my generated list:
012345 / 012368
012345 / 012389
012345 / 012468
012345 / 012489
012345 / 012568
012345 / 012589
012345 / 012678
012345 / 012689
012345 / 012789
:
056789 / 123459
056789 / 123467
056789 / 123468
056789 / 123469
056789 / 123479
056789 / 123489

Hope that helps already, if not, just tell me!

PS I still need hints for 110, 118, 131, 132, 133, 135-143, 146-156!
Top
User avatar
Dreamland Fantasy
Enthusiast
Enthusiast
Posts: 335
Joined: Fri Jun 11, 2004 9:35 pm
Location: Glasgow, UK
Contact:
Contact Dreamland Fantasy

Post by Dreamland Fantasy »

I've just completed problem 146 this morning, but I basically semi-brute forced it and threw the full 12 GHz of my computer at it to complete it in about 4 days. :?

I'll need to try and optimise the code.

Kind regards,

Francis.
Top
User avatar
Michael Vogel
Addict
Addict
Posts: 2797
Joined: Thu Feb 09, 2006 11:27 pm
Contact:
Contact Michael Vogel

Post by Michael Vogel »

Dreamland Fantasy wrote:I've just completed problem 146 [...] in about 4 days. :? [...]
Hi Francis,
I started with something like that:

Code: Select all

s.q=0
n.q=2

	Repeat
	If (n%3<>0) And (n%7<>0) And (n%13<>0) And (n%27<>0)

		nq.q=n*n

		If IsPrime(nq+1)
			If IsPrime(nq+3)
				If IsPrime(nq+5)=#False
					If IsPrime(nq+7)
						If IsPrime(nq+9)
							If IsPrime(nq+11)=#False
								If IsPrime(nq+13)
									If IsPrime(nq+15)=#False
										If IsPrime(nq+17)=#False
											If IsPrime(nq+19)=#False
												If IsPrime(nq+21)=#False
													If IsPrime(nq+23)=#False
														If IsPrime(nq+25)=#False
															If IsPrime(nq+27)
																Debug n
																s+n
															EndIf
														EndIf
													EndIf
												EndIf
											EndIf
										EndIf
									EndIf
								EndIf
							EndIf
						EndIf
					EndIf
				EndIf
			EndIf
		EndIf
	EndIf

	n+2

Until n=1000000

ShowResult(s)
which runs already about an hour to show up the correct result for 1.000.000 - so it would take weeks on my lazy notebook :cry: to get the solution!

So if you have good ideas what to optimize, please let me know 8)

Michael
Top
User avatar
Dreamland Fantasy
Enthusiast
Enthusiast
Posts: 335
Joined: Fri Jun 11, 2004 9:35 pm
Location: Glasgow, UK
Contact:
Contact Dreamland Fantasy

Post by Dreamland Fantasy »

One observation that I made was that n is always a multiple of 10.

I also optimised my original IsPrime() routine which is now as follows:

Code: Select all

Procedure IsPrime(n.q)
  
  Protected i = 3, Root = Sqr(n)
  
  If n % 2 = 0
    ProcedureReturn 0
  EndIf
  
  While i <= Root
    If n % i = 0
      ProcedureReturn 0
    EndIf
    i + 2
  Wend
  
  ProcedureReturn 1
  
EndProcedure
My routine for checking the consecutive primes is:

Code: Select all

Procedure ConsecutivePrime(n)
  
  Protected nSquare.q = n * n
  Protected n1.q = nSquare + 1
  Protected n3.q = nSquare + 3
  Protected n7.q = nSquare + 7
  Protected n9.q = nSquare + 9
  Protected n13.q = nSquare + 13
  Protected n27.q = nSquare + 27
  Protected a.q, b.q, i.q
  
  Macro macro_ConsecutivePrime(a, b)
    If IsPrime(a) = 0
      ProcedureReturn 0
    EndIf
    i = a + 1
    While i < b
      If IsPrime(i)
        ProcedureReturn 0
      EndIf
      i + 1
    Wend
  EndMacro
  
  macro_ConsecutivePrime(n1, n3)
  macro_ConsecutivePrime(n3, n7)
  macro_ConsecutivePrime(n7, n9)
  macro_ConsecutivePrime(n9, n13)
  macro_ConsecutivePrime(n13, n27)
  If IsPrime(n27) = 0
    ProcedureReturn 0
  EndIf
  
  ProcedureReturn 1
  
EndProcedure
Apparently there is a way to significantly reduce the amount of numbers that you need to check, but I haven't gotten around to working out how to do that yet.

Kind regards,

Francis
Top
User avatar
Michael Vogel
Addict
Addict
Posts: 2797
Joined: Thu Feb 09, 2006 11:27 pm
Contact:
Contact Michael Vogel

Post by Michael Vogel »

Hi Francis,

thanks for your hints and showing your approach!
Dreamland Fantasy wrote:One observation that I made was that n is always a multiple of 10.
that's cool - this reduces the amount of numbers to check to 10%, my first approach checked around 25% of all numbers, so it should be around 2.5 times faster!
Dreamland Fantasy wrote:I also optimised my original IsPrime()...
Hmm, I believe, caching (some) primes would increase the speed of your routine, maybe you'll like to try out if my code would push down calculation time (I'm quite sure)...

Code: Select all

#MaxPrimeCache=79000;	(that's just for the primes up to a million)
Global Dim PrimeCache.q(#MaxPrimeCache)
	Global PrimeCacheCount

	Procedure IsPrime(n.q)
		Protected i=1
		Protected d=2
		Protected Root

		If n=1
			ProcedureReturn #False
		ElseIf n&1=0
			ProcedureReturn #False
		Else
			Root=Sqr(n)
			While d<=Root
				If n%d=0
					ProcedureReturn #False
				EndIf
				If i<PrimeCacheCount
					i+1
					d=PrimeCache(i)
				Else
					d+(9-d%6)>>1; (c) by me!
				EndIf
			Wend
			ProcedureReturn #True
		EndIf
	EndProcedure
	Procedure InitPrimeCache()
		Protected p.q
		PrimeCache(1)=2
		PrimeCacheCount=1

		p=1
		Repeat
			p+2
			If IsPrime(p)
				PrimeCacheCount+1
				PrimeCache(PrimeCacheCount)=p
			EndIf
		Until PrimeCacheCount=#MaxPrimeCache
	EndProcedure

	InitPrimeCache()
Dreamland Fantasy wrote:My routine for checking the consecutive primes is...
Interesting approach, hard to say for me, if the amount of (the long taking) prime tests within your routine is higher or lower than in my approach - a global counter in the IsPrime() procedures would show...

If I have a chance to get access to a faster PC I will try to do the calculation soon...

One question, is 1/10 of all "correct" numbers a prime?

Thanks,
Michael
Top
User avatar
Dreamland Fantasy
Enthusiast
Enthusiast
Posts: 335
Joined: Fri Jun 11, 2004 9:35 pm
Location: Glasgow, UK
Contact:
Contact Dreamland Fantasy

Post by Dreamland Fantasy »

Michael Vogel wrote:Hmm, I believe, caching (some) primes would increase the speed of your routine, maybe you'll like to try out if my code would push down calculation time (I'm quite sure)...
Yes, that is a LOT faster.
Michael Vogel wrote:One question, is 1/10 of all "correct" numbers a prime?
It might be my tiredness just now but I don't quite understand the question.

I was able to speed up my original code further by applying some of the eliminations that you incorporated:

Code: Select all

Procedure ConsecutivePrime(n)
  
  Protected nSquare.q = n * n
  Protected n1.q = nSquare + 1
  Protected n3.q = nSquare + 3
  Protected n7.q = nSquare + 7
  Protected n9.q = nSquare + 9
  Protected n13.q = nSquare + 13
  Protected n27.q = nSquare + 27
  Protected a.q, b.q, i.q
  
  If n % 3 And n % 13 And n % 27
    If n % 7 = 3 Or n % 7 = 4
      
      Macro macro_ConsecutivePrime(a, b)
        If IsPrime(a) = 0
          ProcedureReturn 0
        EndIf
        i = a + 1
        While i < b
          If IsPrime(i)
            ProcedureReturn 0
          EndIf
          i + 1
        Wend
      EndMacro
      
      macro_ConsecutivePrime(n1, n3)
      macro_ConsecutivePrime(n3, n7)
      macro_ConsecutivePrime(n7, n9)
      macro_ConsecutivePrime(n9, n13)
      macro_ConsecutivePrime(n13, n27)
      If IsPrime(n27) = 0
        ProcedureReturn 0
      EndIf
      
      ProcedureReturn 1
      
    Else

      ProcedureReturn 0
      
    EndIf
  EndIf
  
  
EndProcedure
You will also notice that I have made a slight modification to your check by testing if n % 7 is either 3 or 4 which will give you a significant speed increase.

Kind regards,

Francis.
Top
User avatar
Dreamland Fantasy
Enthusiast
Enthusiast
Posts: 335
Joined: Fri Jun 11, 2004 9:35 pm
Location: Glasgow, UK
Contact:
Contact Dreamland Fantasy

Post by Dreamland Fantasy »

I've managed to remove a lot of unncessary number crunching! :)

Code: Select all

Procedure ConsecutivePrime(n)
  
  Protected nSquare.q = n * n
  Protected a.q, b.q, i.q
  
  If n % 3 And n % 13 And n % 27
    If n % 7 = 3 Or n % 7 = 4
      If IsPrime(nSquare + 1)
        If IsPrime(nSquare + 3)
          If IsPrime(nSquare + 7)
            If IsPrime(nSquare + 9)
              If IsPrime(nSquare + 13)
                If IsPrime(nSquare + 27)
                  ProcedureReturn 1
                EndIf
              EndIf
            EndIf
          EndIf
        EndIf
      EndIf
    EndIf
  EndIf
  
EndProcedure
Kind regards,

Francis.
Top
michaeled314
Enthusiast
Enthusiast
Posts: 340
Joined: Tue Apr 24, 2007 11:14 pm

Post by michaeled314 »

How wood you do euler #1 in ASM with no divisions
Top
User avatar
Michael Vogel
Addict
Addict
Posts: 2797
Joined: Thu Feb 09, 2006 11:27 pm
Contact:
Contact Michael Vogel

Post by Michael Vogel »

Dreamland Fantasy wrote:I've managed to remove a lot of unncessary number crunching! :)

Code: Select all

Procedure ConsecutivePrime(n)
  
  Protected nSquare.q = n * n
  Protected a.q, b.q, i.q
  
  If n % 3 And n % 13 And n % 27
    If n % 7 = 3 Or n % 7 = 4
      [...]
    EndIf
  EndIf
  
EndProcedure
Hi Francis,

the first If statement is clear for me (I had that already in the first post), but why you know that the number modulo 7 must have the result 3 or 4?

To speed the whole thing up, I only checked primes*10 and found one (only) additional matching number: 130116970. But the result in Euler was wrong, so it seems that I have to check also non primes :cry: !

I am using also two IsPrime procedures now, the following for the n*n+1 check and, if positive, the normal for n*n+3, n*n+7 etc.

Code: Select all

Procedure IsPrimeChain(n.q)
	Protected i=1
	Protected d=2
	Protected t
	Protected Root

	If n=1
		ProcedureReturn #False
	ElseIf n&1=0
		ProcedureReturn #False
	Else
		Root=Sqr(n)

		While d<=Root
			t=n%d
			If t=0
				ProcedureReturn #False
			ElseIf t+2=d
				ProcedureReturn #False
			ElseIf t+6=d
				ProcedureReturn #False
			ElseIf t+8=d
				ProcedureReturn #False
			ElseIf t+12=d
				ProcedureReturn #False
			ElseIf t+26=d
				ProcedureReturn #False
			EndIf
			If i<PrimeCacheCount
				i+1
				d=PrimeCache(i)
			Else
				d+(9-d%6)>>1
			EndIf
		Wend
		ProcedureReturn #True
	EndIf
EndProcedure
Top
User avatar
Dreamland Fantasy
Enthusiast
Enthusiast
Posts: 335
Joined: Fri Jun 11, 2004 9:35 pm
Location: Glasgow, UK
Contact:
Contact Dreamland Fantasy

Post by Dreamland Fantasy »

Dreamland Fantasy wrote:I've managed to remove a lot of unncessary number crunching! :)

Code: Select all

Procedure ConsecutivePrime(n)
  
  Protected nSquare.q = n * n
  Protected a.q, b.q, i.q
  
  If n % 3 And n % 13 And n % 27
    If n % 7 = 3 Or n % 7 = 4
      If IsPrime(nSquare + 1)
        If IsPrime(nSquare + 3)
          If IsPrime(nSquare + 7)
            If IsPrime(nSquare + 9)
              If IsPrime(nSquare + 13)
                If IsPrime(nSquare + 27)
                  ProcedureReturn 1
                EndIf
              EndIf
            EndIf
          EndIf
        EndIf
      EndIf
    EndIf
  EndIf
  
EndProcedure
Kind regards,

Francis.
Well that completed in just under 2.5 hours on my machine (including pre-calculating all the primes upto 150 million), but I do get one false positive. :(

All in there are 12 valid numbers.

Kind regards,

Francis.
Top
User avatar
Michael Vogel
Addict
Addict
Posts: 2797
Joined: Thu Feb 09, 2006 11:27 pm
Contact:
Contact Michael Vogel

Post by Michael Vogel »

Dreamland Fantasy wrote:
Well that completed in just under 2.5 hours on my machine (including pre-calculating all the primes upto 150 million), but I do get one false positive. :(

All in there are 12 valid numbers.
Hi Francis, seems that you have a fast machine :)

I have three questions:
- how many primes you've found before reaching 150.000.000? (I think, 8.9xx.xxx)
- what is the first of your twelve "hits" over 1.000.000?
- and is the last one 130.116.970?

Thanks,
Michael
Top
michaeled314
Enthusiast
Enthusiast
Posts: 340
Joined: Tue Apr 24, 2007 11:14 pm

Post by michaeled314 »

How would you do euler #1 in asm w/no divisions
Top
User avatar
Dreamland Fantasy
Enthusiast
Enthusiast
Posts: 335
Joined: Fri Jun 11, 2004 9:35 pm
Location: Glasgow, UK
Contact:
Contact Dreamland Fantasy

Post by Dreamland Fantasy »

Michael Vogel wrote:
Dreamland Fantasy wrote:
Well that completed in just under 2.5 hours on my machine (including pre-calculating all the primes upto 150 million), but I do get one false positive. :(

All in there are 12 valid numbers.
Hi Francis, seems that you have a fast machine :)

I have three questions:
- how many primes you've found before reaching 150.000.000? (I think, 8.9xx.xxx)
- what is the first of your twelve "hits" over 1.000.000?
- and is the last one 130.116.970?

Thanks,
Michael
I'm using a quad-core machine clocked at 3GHz per core. I specially wrote my program so that it would multi-thread to utilise the full speed of the processor.

The number of primes that I pre-calculated to 150 million was 8444397.

The first hit over the million mark was 2525870.

And no, 130116970 is not the last valid number. There's one more after that.

Kind regards,

Francis.
Top
dioxin
User
User
Posts: 97
Joined: Thu May 11, 2006 9:53 pm

Post by dioxin »

michaeled314,
ASM has divisions so why not use them?
On the other hand, divisions can be slow so not using them may save time.

One way to do it would be to set up a 1000 byte array with each location representing a number from 1 to 1000.
Count through the array in steps of 3 and set each third byte
Count through the array in steps of 5 and set each fifth byte.
Scan through the array and see which bytes are set, if set add the array index to the sum so far.

Another way, without needing an array, would be to sum the numbers 3,6,9,etc upto 1000. Sum the numbers 5,10,15,etc. upto 1000 and add it to the first sum then sum the numbers 15,30,45,etc. up to 1000 and subtract it from the previous sum as you don't want to count multiples of 3 AND 5 twice.


Michael,
how many primes you've found before reaching 150.000.000? (I think, 8.9xx.xxx)
I agree with Francis. The total number of primes (including 1) is 8,444,397 and it takes about 10 seconds to extract them on the my "modestly powered computer".




Francis,
since "an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute." then you need to gain by a factor of about 50,000 to come close to succeeding.
I can see some savings in the method being used but nothing of that order.
I think to start with you need a much more efficient IsPrime() function and a more efficient find next prime function.

Paul.
Top
Post Reply

Return to “General Discussion”