Project Euler: Composites with the prime repunit property
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 hereint 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 primeint 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 1int 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 hereint 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 thatbool 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;}}}
