Trusted answers to developer questions

Hammad Qayyum

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

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`

.

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

CONTRIBUTOR

Hammad Qayyum

RELATED COURSES

View all Courses

Keep Exploring

Related Courses