Project Euler/49
From charlesreid1
Problem Statement
The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways:
- (i) each of the three terms is prime
- (ii) each of the 4-digit numbers is a permutation of the same digits
There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes exhibiting this property, but there is one other 4-digit increasing sequence.
What 12-digit number do you form by concatenating the three terms in this sequence?
Approach
Generate 4-Digit Primes
Use a prime sieve to generate all primes up to 10,000. Discard primes below 1,000, leaving only the 4-digit primes.
Group by Digit Permutations
For each 4-digit prime:
- Convert the integer to a string
- Sort its characters (digits) alphabetically
- Use the sorted string as a key in a HashMap
- Append the original prime to the list for that key
After processing all primes, each entry in the map contains a group of primes that are digit permutations of one another.
Find Arithmetic Sequences
For each group containing at least three members:
- Sort the group in ascending order
- Iterate over all pairs (a, b) within the group, where b > a
- Compute the third term: c = b + (b - a)
- If c is also in the group, then (a, b, c) forms an arithmetic progression
Exclude the Known Example
The problem statement gives 1487, 4817, 8147 as an example. Skip the sequence where a = 1487 so that only the other 4-digit sequence is reported.
Return the Concatenation
Concatenate the three terms (a, b, c) as strings and return the resulting 12-digit number.
Solution
Link: https://git.charlesreid1.com/cs/euler/src/branch/main/java/Problem049.java
Flags
