End Of An Era

I made a assumption that the number will be below 9999

I used C code to crack this question as i was not aware about Sphenic number

Here is my code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include<stdio.h>
#include<cstring>
using namespace std;
int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999};
#define MAX 1117
int C[MAX];

int numc(int N)
{
    memset(C,0,sizeof(C));
    int count = 0;
    for(int i = 0;i<MAX;)
    {
        if(N%prime[i]==0)
        {
            if(C[i]==1)
                return 0;
            C[i]++;
            count++;
            N/=prime[i];
        }
        else
            i++;
    }
    if(count==3)
        return 1;
    else
        return 0;
}

int main()
{
    for(int i=2014;i<9999;i++)
    {
        if(numc(i) && numc(i+1) && numc(i+2))
        {   
            printf("The ans is : %d\n",i);
            break;
        }
    }
}

• prime is the list of prime number.

• numc() function return 1 or 0 based on the condition if the argument number N is having 3 distinct prime number then it will return 1 else 0.

• memset() is a function which will initialize all element of array to 0 given in function.

The ans is 2665!

Nice problem. I had heard about sphenic numbers before but I forgot about it (I've been forgetting much stuff recently). Anyway, after I solved the problem for minimum $x$ , I poked around with my code a bit to see if it could be made stronger since my original code had almost negligible run-time. And so.....

Here's a stronger solution that I made in C++14 (gcc-5.1) that generates the list of such numbers upto a range specified by user, i.e.,

Definition: Call a positive integer $k$ a sphenic master if $k,(k+1),(k+2)$ are all sphenic numbers .

Input: A positive integer $t$ via standard input (#stdin).

Output: List of all sphenic masters $\leq t$ .

Here's the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <iostream>
#include <new>
using namespace std;

int main() {
    long i,t;
    bool *x,prime_factors(long);
    cin>>t;
    x=new bool[t+1]();
    for(i=2;i<=t;i++)
        {
            x[i]=prime_factors(i);
            if(x[i]==true && x[i-1]==true && x[i-2]==true)
                cout<<(i-2)<<endl;
        }
    delete []x;
    return 0;
}
bool prime_factors(long n)
    {
        char *range;
        int prime_div_count=0;
        long k,j,temp=n;
        range=new char[n]();
        for(k=2;k<=(n/2);k++)
            {
                if(range[k]==0)
                    {
                        if(n%k==0)
                            {
                                prime_div_count++;
                                temp/=k;
                            }
                        for(j=k;j<=(n/2);j+=k)
                            range[j]='n';
                    }
            }
        if(prime_div_count==0)
            prime_div_count++;
        delete []range;
        return (prime_div_count==3 && temp==1)?true:false;
    }

Explanation: Starting with the main() block, it takes the input $t$ and then dynamically allocates a boolean ( bool ) array of length $(t+1)$ using new and sends the base address of the array to x which is a bool pointer. x[0] denotes the first element of array and x[t] denotes the last element of array. The x[i] 's represent the truth value of " $i$ is a sphenic number". Initially, all elements of the array are set to false . Then, in a loop, x[i] runs through x[2] to x[t] and in the loop, prime_factors() assigns true or false to x[i] according as x[i] is a sphenic number or not. Then it checks if x[i],x[i-1],x[i-2] are all true or not and if they are, that means $(i-2)$ is a sphenic master, so it outputs it along with newline. After the loop terminates, it deallocates the array using delete (this is necessary to avoid memory leaks since dynamic memory allocation happens in heap, not in stack).

Now, what happens in prime_factors() for each x[i] ? Simple. I implemented a slight variant of the popular Sieve of Eratosthenes to find all the primes that are less than $i$ and are factors of $i$ . A counter variable prime_div_count initially set at zero for every x[i] is incremented everytime a prime factor is found. Also, I created a variable temp that holds the value of i initially. temp is then divided once by each prime factor found. If $i$ is sphenic, $t$ will be completely divided and will be $1$ when all primes of $i$ are found and prime_div_count will hold the number of prime factors. So, it's tested if the two conditions for $i$ to be sphenic is met or not. If it's met, then true is returned, else false .

Extra info for those interested: I used a trivial number-theoretic fact while implementing prime_factors() to reduce run-time as much as I could:

If $n$ isn't prime, all the prime factors of $n$ are $\leq\dfrac n2$ .

You can see the code in action and its output here and are free to fork it and test it yourself by giving an input $t$ . Its run-time is about $13.8$ secs for $t=80000$ . I think that the code can be optimized further (in terms of memory usage and run-time) and extended for higher values of $t$ by using better primality testing algorithms and effectively selecting data types for variables but for now, it's more than enough.

Our relevant part of output : $~~~~$ image

In the output list, it's easy to see that $2665$ is the number after $2013$ and hence our answer. $_\square$

See this: Sphenic number

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

//C++
#include <iostream.h>
#include<conio.h>

void main() {

int number,freqi,freq1,freq2=0,start;

for(int x=2000;x<=5000;x++)

{    number=x;
     freq1=0;

for(int i=2;i<=number;i++)
 {    freqi=0;
        while(number%i==0)
     {    number/=i;
                freq1++;
                   freqi++;

        if(freqi>1)
            goto start;
       }
   }
   if(freq1==3)
   {  freq2++;
            if(freq2==3)
      cout<<x-2<<" ";
                      }
else
     freq2=0;

  start:
}

    getch();
}

OUTPUT:

1

2013 2665 3729 

Thus, we have to wait for 650 years for this event to occur again!

$Since~ the~number~N~has~ to~ have~ only~three~prime~factors,~4~can~not~be~one~factor.\\ However~all~N,~N+1,~N+2, ~must~have~only~three~primes~as~factors.\\ If~N \equiv 2 ~\pmod 4, ~the~third~ (last)~N+2 \equiv 0 ~\pmod 4.~~\therefore~divisible~by~4.\\ If~N \equiv 3 ~\pmod 4,~~~the~second~ (middle)~N+1 \equiv 0 ~\pmod 4. ~~\therefore~divisible~by~4. \\ So~we~need~check~only~~N \equiv 1 ~\pmod 4.\\ ~~~\\ I~used~factoring~calculator.~~So~I~started~with~~N=2017.~\\ ~~~\\ {\color{#3D99F6}{(A)}}~Checked~N~if~it~had~only~three~primes~as~factors.\\ If~YES~then~checked~for~N+1, ~~otherwise~skip~to~NO.\\ If~YES~then~checked~for~N+2, ~~otherwise~skip~to~NO.\\ IF~~YES,~this~is~the~solution.\\ ~~~\\ If~NO,~let~~N=N+4,~~and~cycle~again~from~(A).\\ ~~~\\ With~every~NO~I~added~4~till~I~had~YES,~YES,~YES~at~N+2=2667.\\ So~N=\Large~~~\color{#D61F06}{2665}.$

Here is my solution in python 3.4:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from pyprimes import factors

def triprimes(m):
    return len(factors(m)) == 3 and  len(set(factors(m))) == 3

def solve(n):
    "End Of An Era"
    suite = 0
    while(suite < 3):
        n = n + 1
        suite = suite + 1 if triprimes(n) else 0
    return n - 2

print(solve(2013))