Step by Step solution about How to resolve the algorithm Untouchable numbers step by step in the C++ programming language

The provided source code is a C++ program that calculates and displays "untouchable numbers" up to a specified limit. Untouchable numbers are positive integers that cannot be expressed as the sum of two or more distinct coprime positive integers.

Here's a breakdown of the code:

1. Data Structures and Variables:

   • bitset<maxUT+1> N: A bitset used to track untouchable numbers.
   • vector<int> G: A vector containing prime numbers used in the algorithm.
   • array<Z3, dL+1> L: An array of functions that generate untouchable numbers.
   • int sG: The size of the G vector.
   • int mUT: The limit up to which untouchable numbers are calculated.

2. uT Class:

   • The code defines a class uT that encapsulates the functionality for finding untouchable numbers.
   • The constructor uT(const int n) initializes the object with an input limit n.
   • The _g method is a recursive function used to mark all multiples of prime numbers in N.
   • The nxt method finds the next untouchable number greater than or equal to the given number.
   • The fN method is a function generator that generates a sequence of untouchable numbers.
   • The fG method is a function generator that generates a sequence of coprime integers.
   • The fL method initializes the L array of function generators.
   • The count method counts the number of untouchable numbers found up to the limit.

3. main Function:

   • The program has multiple main functions because C++ allows multiple entry points. Each main function performs a specific task:
     • The first main prints the first 30 untouchable numbers below 2000.
     • The second main prints the number of untouchable numbers below 100,000.
     • The third main prints the number of untouchable numbers below 1,000,000.
     • The fourth main prints the number of untouchable numbers below 2,000,000.

How the Algorithm Works:

The algorithm used to find untouchable numbers is based on the following properties:

• Every untouchable number must be coprime with any other untouchable number.
• Every untouchable number greater than 1 can be expressed as (n + i) + (n + i)(n + 2i), where n is an untouchable number and i is a positive integer.

The algorithm initializes the N bitset to all 1s, indicating that all integers are potentially untouchable. It then eliminates all multiples of prime numbers by calling _g.

To generate untouchable numbers, the algorithm uses recursive functions fN and fG. fN generates a sequence of untouchable numbers, and fG generates a sequence of coprime integers that are added to untouchable numbers to generate new untouchable numbers.

The L array of function generators is initialized using fL. Each element of L generates a sequence of untouchable numbers with different coprime integer sequences.

Finally, the program counts the number of untouchable numbers found up to the specified limit using the count method.

// Untouchable Numbers : Nigel Galloway - March 4th., 2021;
#include <functional>
#include <bitset> 
#include <iostream>
#include <cmath>
using namespace std; using Z0=long long; using Z1=optional<Z0>; using Z2=optional<array<int,3>>; using Z3=function<Z2()>;
const int maxUT{3000000}, dL{(int)log2(maxUT)};
struct uT{
  bitset<maxUT+1>N; vector<int> G{}; array<Z3,int(dL+1)>L{Z3{}}; int sG{0},mUT{};
  void _g(int n,int g){if(g<=mUT){N[g]=false; return _g(n,n+g);}}
  Z1 nxt(const int n){if(n>mUT) return Z1{}; if(N[n]) return Z1(n); return nxt(n+1);}
  Z3 fN(const Z0 n,const Z0 i,int g){return [=]()mutable{if(g<sG && ((n+i)*(1+G[g])-n*G[g]<=mUT)) return Z2{{n,i,g++}}; return Z2{};};}
  Z3 fG(Z0 n,Z0 i,const int g){Z0 e{n+i},l{1},p{1}; return [=]()mutable{n=n*G[g]; p=p*G[g]; l=l+p; i=e*l-n; if(i<=mUT) return Z2{{n,i,g}}; return Z2{};};}
  void fL(Z3 n, int g){for(;;){
    if(auto i=n()){N[(*i)[1]]=false; L[g+1]=fN((*i)[0],(*i)[1],(*i)[2]+1); g=g+1; continue;}
    if(auto i=L[g]()){n=fG((*i)[0],(*i)[1],(*i)[2]); continue;}
    if(g>0) if(auto i=L[g-1]()){ g=g-1; n=fG((*i)[0],(*i)[1],(*i)[2]); continue;}
    if(g>0){ n=[](){return Z2{};}; g=g-1; continue;} break;}
  }
  int count(){int g{0}; for(auto n=nxt(0); n; n=nxt(*n+1)) ++g; return g;}
  uT(const int n):mUT{n}{
    N.set(); N[0]=false; N[1]=false; for(auto n=nxt(0);*n<=sqrt(mUT);n=nxt(*n+1)) _g(*n,*n+*n); for(auto n=nxt(0); n; n=nxt(*n+1)) G.push_back(*n); sG=G.size();
    N.set(); N[0]=false; L[0]=fN(1,0,0); fL([](){return Z2{};},0);
  }
};


int main(int argc, char *argv[]) {
  int c{0}; auto n{uT{2000}}; for(auto g=n.nxt(0); g; g=n.nxt(*g+1)){if(c++==30){c=1; printf("\n");} printf("%4d ",*g);} printf("\n");
}


int main(int argc, char *argv[]) {
  int z{100000}; auto n{uT{z}}; cout<<"untouchables below "<<z<<"->"<<n.count()<<endl;
}


int main(int argc, char *argv[]) {
  int z{1000000}; auto n{uT{z}}; cout<<"untouchables below "<<z<<"->"<<n.count()<<endl;
}


int main(int argc, char *argv[]) {
  int z{2000000}; auto n{uT{z}}; cout<<"untouchables below "<<z<<"->"<<n.count()<<endl;
}