Project Euler Problem 26

Problem 26

13 September 2002

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 ¹/₇ has a 6-digit recurring cycle.

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

Answer: 983

 

Fermat’s little theorem

 

C#

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace ConsoleApplication1 {
    class Program {
        static bool isPrime(long x) {
            for (long i = 2; i * i <= x; i++)
                if (x % i == 0) return false;
            return true;
        }

        static void Main(string[] args) {
            // Fermat’s little theorem

            for (long d = 999; d >= 1; d -= 2) {
                if (!isPrime(d)) continue;
                //Console.WriteLine(d);
                long n = 1;
                BigInteger tenpn = 10;
                while (true) {
                    tenpn *= 10;
                    n++;
                    if ((tenpn - 1) % d == 0 || n > d) break;
                }
                if (n == d - 1) {
                    Console.WriteLine(d);
                    break;
                }
            }
        }
    }
}

; Racket

(define (prime? x)
  (let loop ([i 2])
    (if (<= (* i i) x)
        (if (zero? (modulo x i)) 
            #f
            (loop (add1 i)))
        #t)))

; Fermat's little theorem
(let loop ([d 999])
  (when (>= d 1)    
    (if (prime? d)
        (begin
          (let ([n 1]
                [tenpn 10])
            (let loop ()
              (set! tenpn (* tenpn 10))
              (set! n (add1 n))
              (unless (or (zero? (modulo (- tenpn 1) d)) (> n d)) (loop)))
            (if (= n (- d 1))
                (displayln d)
                (loop (- d 2)))))
        (loop (- d 2)))))