2018-09-30 23:01:58 +01:00
---
id: 5900f3ce1000cf542c50fee0
title: 'Problem 97: Large non-Mersenne prime'
2020-11-27 19:02:05 +01:00
challengeType: 5
2019-08-05 09:17:33 -07:00
forumTopicId: 302214
2021-01-13 03:31:00 +01:00
dashedName: problem-97-large-non-mersenne-prime
2018-09-30 23:01:58 +01:00
---
2020-11-27 19:02:05 +01:00
# --description--
2020-02-28 21:39:47 +09:00
2021-05-27 21:38:56 +02:00
The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form $2^{6972593} − 1$; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form $2^p − 1$, have been found which contain more digits.
2020-02-28 21:39:47 +09:00
2021-05-27 21:38:56 +02:00
However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: $28433 × 2^{7830457} + 1$.
2020-02-28 21:39:47 +09:00
2021-05-27 21:38:56 +02:00
Find the last ten digits of that non-Mersenne prime in the form $multiplier × 2^{power} + 1$.
2020-02-28 21:39:47 +09:00
2020-11-27 19:02:05 +01:00
# --hints--
2018-09-30 23:01:58 +01:00
2021-05-27 21:38:56 +02:00
`largeNonMersennePrime(19, 6833086)` should return a string.
2018-09-30 23:01:58 +01:00
2020-11-27 19:02:05 +01:00
```js
2021-05-27 21:38:56 +02:00
assert(typeof largeNonMersennePrime(19, 6833086) === 'string');
2020-11-27 19:02:05 +01:00
```
2018-09-30 23:01:58 +01:00
2021-05-27 21:38:56 +02:00
`largeNonMersennePrime(19, 6833086)` should return the string `3637590017` .
2018-09-30 23:01:58 +01:00
2020-11-27 19:02:05 +01:00
```js
2021-05-27 21:38:56 +02:00
assert.strictEqual(largeNonMersennePrime(19, 6833086), '3637590017');
```
`largeNonMersennePrime(27, 7046834)` should return the string `0130771969` .
```js
assert.strictEqual(largeNonMersennePrime(27, 7046834), '0130771969');
```
`largeNonMersennePrime(6679881, 6679881)` should return the string `4455386113` .
```js
assert.strictEqual(largeNonMersennePrime(6679881, 6679881), '4455386113');
```
`largeNonMersennePrime(28433, 7830457)` should return the string `8739992577` .
```js
assert.strictEqual(largeNonMersennePrime(28433, 7830457), '8739992577');
2018-09-30 23:01:58 +01:00
```
2020-11-27 19:02:05 +01:00
# --seed--
2018-09-30 23:01:58 +01:00
2020-11-27 19:02:05 +01:00
## --seed-contents--
2018-09-30 23:01:58 +01:00
```js
2021-05-27 21:38:56 +02:00
function largeNonMersennePrime(multiplier, power) {
2020-09-15 09:57:40 -07:00
2018-09-30 23:01:58 +01:00
return true;
}
2021-05-27 21:38:56 +02:00
largeNonMersennePrime(19, 6833086);
2018-09-30 23:01:58 +01:00
```
2020-11-27 19:02:05 +01:00
# --solutions--
2018-09-30 23:01:58 +01:00
```js
2021-05-27 21:38:56 +02:00
function largeNonMersennePrime(multiplier, power) {
function modStepsResults(number, other, mod, startValue, step) {
let result = startValue;
for (let i = 0; i < other ; i + + ) {
result = step(number, result) % mod;
}
return result;
}
const numOfDigits = 10;
const mod = 10 ** numOfDigits;
const digitsAfterPower = modStepsResults(2, power, mod, 1, (a, b) => a * b);
const digitsAfterMultiply = modStepsResults(
digitsAfterPower,
multiplier,
mod,
0,
(a, b) => a + b
);
const lastDigits = (digitsAfterMultiply + 1) % mod;
return lastDigits.toString().padStart(10, '0');
}
2018-09-30 23:01:58 +01:00
```