Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

project euler
composites
prime
repunit

Project Euler: Composites with the prime repunit property

Hammad Qayyum

Problem

Given that n is a positive integer and GCD(n, 10) = 1, it can be shown that there always exists a value, k, for which R(k) is divisible by n. Let A(n) be the least such value of k; for example, A(7) = 6 and A(41) = 5.

You are given that for all primes, p > 5, and that p − 1 is divisible by A( p). For example, when p = 41, then A(41) = 5, and 40 is divisible by 5.

However, there are rare composite values for which this is also true, the first five examples being 91, 259, 451, 481, and 703.

Find the sum of the first twenty-five composite values of n for which GCD(n, 10) = 1 and n − 1 is divisible by A(n).

Source of problem: https://projecteuler.net/problem=130

What is a repunit?

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k.

For example:
R(9) = 111111111,
R(2) = 11.

Solution

This problem can easily be solved by brute force. We will first calculate the term A(n). It is calculated with the following function, which is also used in other problems.

Then, we will check if n-1 is divisible by A(n) or not, given that n is not a prime number. We will use the GCD function to calculate the factors. The following is the complete code to solve the above solution.

using System;
namespace euler {
    class PrimeComposites {
        static void Main(string[] args) {
            new PrimeComposites().Bruteforce();
        }
        void Bruteforce() {    
            // calculating the answer with limit of 25 composite number
            // initializing result , limits and counters here        
            int l = 25, f = 0 , n = 1, res = 0;
            while (f < l) {
                n++;
                if (IsPrime(n)) continue;  // we require composities numbers so skipping the code if the number is prime
                int a = A(n);
                if (a != 0 && ((n - 1) % a == 0)) {
                    res += n;
                    f++;                    
                }   
            }
            Console.WriteLine("Sum : {0}", res);
        }
        // calculating the term A(n) here except when the GCD of the number and 10 is 1
        int A(int n) {
            if (GCD(n, 10) != 1) return 0;
            int x = 1, k=1;
            while (x != 0) {
                x = (x * 10 + 1) % n;
                k++;
            }
            return k;
        }
        // calculating thr Value of GCD here
        int GCD(int a, int b) {
            return b == 0 ? a : GCD(b, a % b);
        }
        // checkinh if the person is prime and return the boolean answer according to that
        bool IsPrime(int n) {
            if (n < 2 || n % 2 == 0 || n % 3 == 0)
                return false;
            if (n < 4 || n < 9 || n < 25)
                return true;
            int s = (int)Math.Sqrt(n);
            for (int i = 5; i <= s; i += 6) {
                if (n % i == 0)
                    return false;
                if (n % (i + 2) == 0)
                    return false;
            }
            return true;
        }   
    }
}

RELATED TAGS

project euler
composites
prime
repunit
RELATED COURSES

View all Courses

Keep Exploring