PureBasic Forums - English

Posted: **Thu Aug 02, 2007 4:50 am**

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

)

I come up with 38 different arrangements.

Posted: **Thu Aug 02, 2007 10:28 pm**

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 )

I come up with 38 different arrangements.

Ui, it's just some weeks ago and I've already problems to understand my own solution

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!

Posted: **Sat Aug 11, 2007 9:57 am**

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.

Posted: **Sat Aug 11, 2007 11:42 am**

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

to get the solution!

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

Michael

Posted: **Sat Aug 11, 2007 5:31 pm**

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

Posted: **Sat Aug 11, 2007 9:41 pm**

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

Posted: **Sun Aug 12, 2007 12:43 am**

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.

Posted: **Sun Aug 12, 2007 1:02 am**

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.

Posted: **Sun Aug 12, 2007 2:45 am**

How wood you do euler #1 in ASM with no divisions

Posted: **Sun Aug 12, 2007 9:20 am**

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

!

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

Posted: **Sun Aug 12, 2007 9:21 am**

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.

Posted: **Sun Aug 12, 2007 2:27 pm**

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

Posted: **Sun Aug 12, 2007 4:00 pm**

How would you do euler #1 in asm w/no divisions

Posted: **Sun Aug 12, 2007 8:01 pm**

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.

Posted: **Sun Aug 12, 2007 9:41 pm**

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.

PureBasic Forums - English

Project Euler...