Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Feature/count distinct powers#1742

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Open
abda-gaye wants to merge6 commits intoTheAlgorithms:master
base:master
Choose a base branch
Loading
fromabda-gaye:feature/count-distinct-powers
Open
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
56 changes: 56 additions & 0 deletionsProject-Euler/Problem026.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
/**
* Problem - Longest Recurring Cycle
*
* @see {@link https://projecteuler.net/problem=26}
*
* Find the value of denominator < 1000 for which 1/denominator contains the longest recurring cycle in its decimal fraction part.
*/

/**
* Main function to find the denominator < limit with the longest recurring cycle in 1/denominator.
*
* @param {number} limit - The upper limit for the denominator (exclusive).
* @returns {number} The denominator that has the longest recurring cycle in its decimal fraction part.
*/
function findLongestRecurringCycle(limit) {
/**
* Calculates the length of the recurring cycle for 1 divided by a given denominator.
*
* @param {number} denominator - The denominator of the unit fraction (1/denominator).
* @returns {number} The length of the recurring cycle in the decimal part of 1/denominator.
*/
function getRecurringCycleLength(denominator) {
const remainderPositions = new Map()
let numerator = 1
let position = 0

while (numerator !== 0) {
if (remainderPositions.has(numerator)) {
return position - remainderPositions.get(numerator)
}

remainderPositions.set(numerator, position)

numerator = (numerator * 10) % denominator
position++
}

return 0
}

let maxCycleLength = 0
let denominatorWithMaxCycle = 0

for (let denominator = 2; denominator < limit; denominator++) {
const cycleLength = getRecurringCycleLength(denominator)

if (cycleLength > maxCycleLength) {
maxCycleLength = cycleLength
denominatorWithMaxCycle = denominator
}
}

return denominatorWithMaxCycle
}

export { findLongestRecurringCycle }
51 changes: 51 additions & 0 deletionsProject-Euler/Problem027.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
/**
* Problem - Quadratic Primes
*
* @see {@link https://projecteuler.net/problem=27}
*
* The quadratic expression n^2 + an + b, where |a| < 1000 and |b| ≤ 1000,
* produces a positive prime for consecutive values of n, starting with n = 0.
* Find the product of the coefficients, a and b, for the quadratic expression that
* produces the maximum number of primes for consecutive values of n.
*/

/**
* Main function to find the coefficients a and b that produce the maximum number
* of consecutive primes for the quadratic expression n^2 + an + b.
*
* @returns {{maxPrimes: number, product: number}} An object containing the maximum number of primes
* and the product of coefficients a and b.
*/
function findMaxConsecutivePrimes() {
function isPrime(n) {
if (n < 2) return false
if (n === 2) return true
if (n % 2 === 0) return false
for (let i = 3; i <= Math.sqrt(n); i += 2) {
if (n % i === 0) return false
}
return true
}

let maxPrimes = 0
let product = 0

for (let a = -999; a < 1000; a++) {
for (let b = -1000; b <= 1000; b++) {
let n = 0
while (true) {
const result = n * n + a * n + b
if (result < 0 || !isPrime(result)) break
n++
}
if (n > maxPrimes) {
maxPrimes = n
product = a * b
}
}
}

return { maxPrimes, product }
}

export { findMaxConsecutivePrimes }
39 changes: 39 additions & 0 deletionsProject-Euler/Problem029.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
/**
* Problem - Distinct Powers
*
* Find the number of distinct terms generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100.
*/

/**
* Main function to count distinct powers a^b.
*
* @param {number} minA
* @param {number} maxA
* @param {number} minB
* @param {number} maxB
* @returns {number}
*/
function countDistinctPowers(minA, maxA, minB, maxB) {
/**
* Set to store distinct terms generated by a^b.
*/
const distinctTerms = new Set()

for (let a = minA; a <= maxA; a++) {
for (let b = minB; b <= maxB; b++) {
distinctTerms.add(Math.pow(a, b))
}
}

return distinctTerms.size
}

const minA = 2
const maxA = 100
const minB = 2
const maxB = 100

const result = countDistinctPowers(minA, maxA, minB, maxB)
console.log(`Number of distinct terms: ${result}`)

export { countDistinctPowers }
16 changes: 16 additions & 0 deletionsProject-Euler/test/Problem026.test.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
import { findLongestRecurringCycle } from '../Problem026'

/**
* Tests for the findLongestRecurringCycle function.
*/
describe('findLongestRecurringCycle', () => {
it.each([
{ limit: 10, expected: 7 },
{ limit: 1000, expected: 983 }, // The denominator with the longest cycle for limit of 1000
{ limit: 4, expected: 3 },
{ limit: 2, expected: 0 } // No cycle for fractions 1/1 and 1/2
])('should return $expected for limit of $limit', ({ limit, expected }) => {
const result = findLongestRecurringCycle(limit)
expect(result).toBe(expected)
})
})
9 changes: 9 additions & 0 deletionsProject-Euler/test/Problem027.test.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
import { findMaxConsecutivePrimes } from '../Problem027'

describe('Problem 027 - Quadratic Primes', () => {
test('should return the correct product of coefficients for max consecutive primes', () => {
const { maxPrimes, product } = findMaxConsecutivePrimes()
expect(maxPrimes).toBe(71)
expect(product).toBe(-59231)
})
})
20 changes: 20 additions & 0 deletionsProject-Euler/test/Problem029.test.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
import { countDistinctPowers } from '../Problem029'

/**
* Tests for the countDistinctPowers function.
*/
describe('countDistinctPowers', () => {
it.each([
{ minA: 2, maxA: 5, minB: 2, maxB: 5, expected: 15 },
{ minA: 2, maxA: 100, minB: 2, maxB: 100, expected: 9183 },
{ minA: 2, maxA: 2, minB: 2, maxB: 2, expected: 1 },
{ minA: 3, maxA: 3, minB: 2, maxB: 5, expected: 4 },
{ minA: 10, maxA: 10, minB: 2, maxB: 5, expected: 4 }
])(
'should return $expected for ranges $minA to $maxA and $minB to $maxB',
({ minA, maxA, minB, maxB, expected }) => {
const result = countDistinctPowers(minA, maxA, minB, maxB)
expect(result).toBe(expected)
}
)
})
[8]ページ先頭
©2009-2025 Movatter.jp