How to resolve the algorithm Sphenic numbers step by step in the C# programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Sphenic numbers step by step in the C# programming language

Table of Contents

Problem Statement

A sphenic number is a positive integer that is the product of three distinct prime numbers. More technically it's a square-free 3-almost prime (see Related tasks below). For the purposes of this task, a sphenic triplet is a group of three sphenic numbers which are consecutive. Note that sphenic quadruplets are not possible because every fourth consecutive positive integer is divisible by 4 (= 2 x 2) and its prime factors would not therefore be distinct. 30 (= 2 x 3 x 5) is a sphenic number and is also clearly the first one. [1309, 1310, 1311] is a sphenic triplet because 1309 (= 7 x 11 x 17), 1310 (= 2 x 5 x 31) and 1311 (= 3 x 19 x 23) are 3 consecutive sphenic numbers. Calculate and show here:

  1. All sphenic numbers less than 1,000.
  2. All sphenic triplets less than 10,000.
  3. How many sphenic numbers are there less than 1 million?
  4. How many sphenic triplets are there less than 1 million?
  5. What is the 200,000th sphenic number and its 3 prime factors?
  6. What is the 5,000th sphenic triplet? Hint: you only need to consider sphenic numbers less than 1 million to answer 5. and 6.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sphenic numbers step by step in the C# programming language

The code finds sphenic numbers and sphenic triplets up to a given bound (1,000,000 in this case). A sphenic number is a number that is the product of three distinct prime numbers. A sphenic triplet is a set of three consecutive sphenic numbers.

The code first generates a list of all the prime numbers up to the given bound using the Sieve of Eratosthenes. Then, it iterates over all the pairs of prime numbers and checks if their product is less than the given bound. If it is, then the code checks if the product of the two prime numbers and a third prime number is less than the given bound. If it is, then the code yields the product as a sphenic number.

The code also defines a method called Consecutive that takes an enumerable of integers and returns an enumerable of consecutive integers that are separated by 1. This method is used to find sphenic triplets.

The code then prints out the first 1000 sphenic numbers and the first 5000 sphenic triplets. It also prints out the number of sphenic numbers and sphenic triplets found up to the given bound.

Finally, the code prints out the 200,000th sphenic number and the 5,000th sphenic triplet.

Source code in the csharp programming language

using System.Linq;
using System.Collections.Generic;
using static System.Console;

public static class SphenicNumbers
{
    public static void Main()
    {
        var numbers = FindSphenicNumbers(1_000_000).OrderBy(t => t.N).ToList();
        var triplets = numbers.Select(t => t.N).Consecutive().ToList();

        WriteLine("Sphenic numbers up to 1 000");
        numbers.Select(t => t.N).TakeWhile(n => n < 1000).Chunk(15)
            .Select(row => row.Delimit()).ForEach(WriteLine);
        WriteLine();

        WriteLine("Sphenic triplets up to 10 000");
        triplets.TakeWhile(n => n < 10_000).Select(n => (n-2, n-1, n)).Chunk(3)
            .Select(row => row.Delimit()).ForEach(WriteLine);
        WriteLine();

        WriteLine($"Number of sphenic numbers < 1 000 000: {numbers.Count}");
        WriteLine($"Number of sphenic triplets < 1 000 000: {triplets.Count}");
        var (n, (a, b, c)) = numbers[199_999];
        WriteLine($"The 200 000th sphenic number: {n} = {a} * {b} * {c}");
        int t = triplets[4_999];
        WriteLine($"The 5 000th sphenic triplet: {(t-2, t-1, t)}");
    }

    static IEnumerable<(int N, (int, int, int) Factors)> FindSphenicNumbers(int bound)
    {
        var primes = PrimeMath.Sieve(bound / 6).ToList();
        for (int i = 0; i < primes.Count; i++) {
            for (int j = i + 1; j < primes.Count; j++) {
                int p = primes[i] * primes[j];
                if (p >= bound) break;
                for (int k = j + 1; k < primes.Count; k++) {
                    if (primes[k] > bound / p) break;
                    int n = p * primes[k];
                    yield return (n, (primes[i], primes[j], primes[k]));
                }
            }
        }
    }

    static IEnumerable<int> Consecutive(this IEnumerable<int> source)
    {
        var (a, b, c) = (0, 0, 0);
        foreach (int d in source) {
            (a, b, c) = (b, c, d);
            if (b - a == 1 && c - b == 1) yield return c;
        }
    }

    static string Delimit<T>(this IEnumerable<T> source, string separator = " ") =>
        string.Join(separator, source);

    static void ForEach<T>(this IEnumerable<T> source, Action<T> action)
    {
        foreach (T element in source) action(element);
    }
}


  

You may also check:How to resolve the algorithm Sorting algorithms/Stooge sort step by step in the COBOL programming language
You may also check:How to resolve the algorithm Chinese remainder theorem step by step in the OCaml programming language
You may also check:How to resolve the algorithm First perfect square in base n with n unique digits step by step in the Haskell programming language
You may also check:How to resolve the algorithm Hello world/Text step by step in the Lasso programming language
You may also check:How to resolve the algorithm Ludic numbers step by step in the PowerShell programming language