[Tutor] Problem Euler 26

kinuthiA muchanE muchanek at gmail.com
Sun Jun 29 22:34:33 CEST 2008


Hi,
I am trying to solve Problem Number 26
(http://projecteuler.net/index.php?section=problems&id=26) on project
Euler but apparently the answer I am submitting is wrong.

Here is the problem:


A unit fraction contains 1 in the numerator. The decimal representation
of the unit fractions with denominators 2 to 10 are given:

        1/2
        = 
        0.5
        1/3
        = 
        0.(3)
        1/4
        = 
        0.25
        1/5
        = 
        0.2
        1/6
        = 
        0.1(6)
        1/7
        = 
        0.(142857)
        1/8
        = 
        0.125
        1/9
        = 
        0.(1)
        1/10
        = 
        0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It
can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring
cycle in its decimal fraction part.

I am giving the answer 38, because 1/38 = 0.0263157894. It seems I have
misunderstood the question or I cant solve it! Here is the code that I
came up with:

def aux(num):
	import re
	pattern = re.compile(r"^0?1?2?3?4?5?6?7?8?9?$")

	frac ="%.9f"%(1.0/num) 
	fracSlice = frac[2:] 			# get the decimal fractional part, ie remove
'0.'
	
	fracList = list(fracSlice) 		#convert string to a list
	fracList.sort() 				# I need to sort , because I will be searching by
increasing order
	
	testFrac  = "".join(fracList) 	# convert list back to a string, phew!
	if re.match(pattern,testFrac):  # if the pattern matches, the number is
our candidate
		print (num,fracSlice)
	
		
for b in xrange(1,1000):
	aux(b)

Er... er, that does not exactly work as expected but it narrows the
search to only 3 candidates because of the inclusion of the zero:

 (28, '035714286')
 (38, '026315789')
 (81, '012345679')

For 28, the digit, in the fractional part, after 8 is 5, so 5 is
repeated and as for, 81 the next digit after 7 is 0, so again 0 occurs
twice. But for 38, the next digit after 9 is 4, and because it has NOT
occurred before, I assume 38 is the correct answer... and I am wrong! 

I suspect I have completely misunderstood the question.

Any ideas?
Thanks!

Kinuthia...
	 

   






More information about the Tutor mailing list