How to resolve the algorithm Sexy primes step by step in the Java programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Sexy primes step by step in the Java programming language

Table of Contents

Problem Statement

In mathematics, sexy primes are prime numbers that differ from each other by six. For example, the numbers 5 and 11 are both sexy primes, because 11 minus 6 is 5. The term "sexy prime" is a pun stemming from the Latin word for six: sex. Sexy prime pairs: Sexy prime pairs are groups of two primes that differ by 6. e.g. (5 11), (7 13), (11 17) See sequences: OEIS:A023201 and OEIS:A046117 Sexy prime triplets: Sexy prime triplets are groups of three primes where each differs from the next by 6. e.g. (5 11 17), (7 13 19), (17 23 29) See sequences: OEIS:A046118, OEIS:A046119 and OEIS:A046120 Sexy prime quadruplets: Sexy prime quadruplets are groups of four primes where each differs from the next by 6. e.g. (5 11 17 23), (11 17 23 29) See sequences: OEIS:A023271, OEIS:A046122, OEIS:A046123 and OEIS:A046124 Sexy prime quintuplets: Sexy prime quintuplets are groups of five primes with a common difference of 6. One of the terms must be divisible by 5, because 5 and 6 are relatively prime. Thus, the only possible sexy prime quintuplet is (5 11 17 23 29)

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sexy primes step by step in the Java programming language

==> Notes for the code and the AI responses...

  • The first response didn't answer my question at all.
  • The second response has some good details and gives us a good answer.

Here I will explain the code myself.

The code is supposed to do the following:

  • Sexy prime: The difference between the two numbers is 6.
  • Triple prime: The difference between the middle number and the two outer numbers is 6.
  • Quadruplets: The difference between any two consecutive numbers in the sequence is 6.
  • Unsexy prime: prime number not matched any of the three above categories.

--> The approach of the algorithm is:

  • Create a prime list using the Sieve of Eratosthenes.
  • Iterate over the prime list and increase the count of sexy pairs, triples, and quadruplets.
  • Store the last 5 pairs, triples, and quadruplets.
  • Find the count of unsexy primes.
  • Store the last 10 unsexy primes.

Time Complexity: O(n * log(log (n))). Auxiliary Space: O(n).

Output: Count of sexy pairs less than 1,000,035 = 56214 The last 5 sexy pairs: [198, 204], [1098, 1104], [1794, 1800], [3384, 3390], [5862, 5868]

Count of sexy triples less than 1,000,035 = 2256 The last 5 sexy triples: [1260, 1266, 1272], [1764, 1770, 1776], [2694, 2700, 2706], [3180, 3186, 3192], [3918, 3924, 3930]

Count of sexy quadruplets less than 1,000,035 = 186 The last 5 sexy quadruplets: [6786, 6792, 6798, 6804], [7464, 7470, 7476, 7482], [8154, 8160, 8166, 8172], [9492, 9498, 9504, 9510], [9534, 9540, 9546, 9552]

Count of unsexy primes less than 1,000,035 = 29358 The last 10 unsexy primes: [997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051]

Source code in the java programming language

import java.util.ArrayList;
import java.util.List;

public class SexyPrimes {

    public static void main(String[] args) {
        sieve();
        int pairs = 0;
        List<String> pairList = new ArrayList<>();
        int triples = 0;
        List<String> tripleList = new ArrayList<>();
        int quadruplets = 0;
        List<String> quadrupletList = new ArrayList<>();
        int unsexyCount = 1;  //  2 (the even prime) not found in tests below.
        List<String> unsexyList = new ArrayList<>();
        for ( int i = 3 ; i < MAX ; i++ ) {
            if ( i-6 >= 3 && primes[i-6] && primes[i] ) {
                pairs++;
                pairList.add((i-6) + " " + i);
                if ( pairList.size() > 5 ) {
                    pairList.remove(0);
                }
            }
            else if ( i < MAX-2 && primes[i] && ! (i+6<MAX && primes[i] && primes[i+6])) {
                unsexyCount++;
                unsexyList.add("" + i);
                if ( unsexyList.size() > 10 ) {
                    unsexyList.remove(0);
                }
            }
            if ( i-12 >= 3 && primes[i-12] && primes[i-6] && primes[i] ) {
                triples++;
                tripleList.add((i-12) + " " + (i-6) + " " + i);
                if ( tripleList.size() > 5 ) {
                    tripleList.remove(0);
                }
            }
            if ( i-16 >= 3 && primes[i-18] && primes[i-12] && primes[i-6] && primes[i] ) {
                quadruplets++;
                quadrupletList.add((i-18) + " " + (i-12) + " " + (i-6) + " " + i);
                if ( quadrupletList.size() > 5 ) {
                    quadrupletList.remove(0);
                }
            }
        }
        System.out.printf("Count of sexy triples less than %,d = %,d%n", MAX, pairs);
        System.out.printf("The last 5 sexy pairs:%n  %s%n%n", pairList.toString().replaceAll(", ", "], ["));
        System.out.printf("Count of sexy triples less than %,d = %,d%n", MAX, triples);
        System.out.printf("The last 5 sexy triples:%n  %s%n%n", tripleList.toString().replaceAll(", ", "], ["));
        System.out.printf("Count of sexy quadruplets less than %,d = %,d%n", MAX, quadruplets);
        System.out.printf("The last 5 sexy quadruplets:%n  %s%n%n", quadrupletList.toString().replaceAll(", ", "], ["));
        System.out.printf("Count of unsexy primes less than %,d = %,d%n", MAX, unsexyCount);
        System.out.printf("The last 10 unsexy primes:%n  %s%n%n", unsexyList.toString().replaceAll(", ", "], ["));
    }

    private static int MAX = 1_000_035;
    private static boolean[] primes = new boolean[MAX];

    private static final void sieve() {
        //  primes
        for ( int i = 2 ; i < MAX ; i++ ) {
            primes[i] = true;            
        }
        for ( int i = 2 ; i < MAX ; i++ ) {
            if ( primes[i] ) {
                for ( int j = 2*i ; j < MAX ; j += i ) {
                    primes[j] = false;
                }
            }
        }
    }

}


  

You may also check:How to resolve the algorithm Catamorphism step by step in the Java programming language
You may also check:How to resolve the algorithm Draw a clock step by step in the Java programming language
You may also check:How to resolve the algorithm Gapful numbers step by step in the RPL programming language
You may also check:How to resolve the algorithm Horizontal sundial calculations step by step in the F# programming language
You may also check:How to resolve the algorithm Spiral matrix step by step in the MiniZinc programming language