Sphenic numbers
Sphenic numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
- Definitions
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.
- Examples
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.
- Task
Calculate and show here:
1. All sphenic numbers less than 1,000.
2. All sphenic triplets less than 10,000.
- Stretch
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.
- References
- Wikipedia: Sphenic number
- OEIS:A007304 - Sphenic numbers
- OEIS:A165936 - Sphenic triplets (in effect)
- Related tasks
AppleScript
use AppleScript version "2.4" -- OS X 10.10 (Yosemite) or later
use framework "Foundation" -- For the sort in getSphenicsBelow().
-- use scripting additions
on sieveOfEratosthenes(limit)
set mv to missing value
if (limit < 2) then return {}
script o
property numberList : prefabList(limit, mv)
end script
set o's numberList's second item to 2
set o's numberList's third item to 3
repeat with n from 5 to limit by 6
set o's numberList's item n to n
tell (n + 2) to set o's numberList's item it to it
end repeat
repeat with n from (limit + 1) to ((count o's numberList) - 3)
set o's numberList's item n to mv
end repeat
repeat with n from 5 to (limit ^ 0.5 div 1) by 6
if (o's numberList's item n is n) then
repeat with multiple from (n * n) to limit by n
set item multiple of o's numberList to mv
end repeat
end if
tell (n + 2)
if (o's numberList's item it is it) then
repeat with multiple from (it * it) to limit by it
set item multiple of o's numberList to mv
end repeat
end if
end tell
end repeat
return o's numberList's numbers
end sieveOfEratosthenes
on prefabList(|size|, filler)
if (|size| < 1) then return {}
script o
property lst : {filler}
end script
set counter to 1
repeat until (counter + counter > |size|)
set o's lst to o's lst & o's lst
set counter to counter + counter
end repeat
if (counter < |size|) then set o's lst to o's lst & o's lst's items 1 thru (|size| - counter)
return o's lst
end prefabList
on getSphenicsBelow(limit)
set limit to limit - 1
script o
property primes : sieveOfEratosthenes(limit div 6)
property sphenics : prefabList(limit, missing value)
end script
set i to 0
repeat with a from 3 to (count o's primes)
set x to o's primes's item a
repeat with b from 2 to (a - 1)
set y to x * (o's primes's item b)
if (y ≥ limit) then exit repeat
repeat with c from 1 to (b - 1)
set z to y * (o's primes's item c)
if (z > limit) then exit repeat
set i to i + 1
set o's sphenics's item i to z
end repeat
end repeat
end repeat
set o's sphenics to o's sphenics's items 1 thru i
return ((current application's class "NSArray"'s arrayWithArray:(o's sphenics))'s ¬
sortedArrayUsingSelector:("compare:")) as list
end getSphenicsBelow
on join(lst, delim)
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to delim
set txt to lst as text
set AppleScript's text item delimiters to astid
return txt
end join
on primeFactors(n)
set output to {}
set limit to (n ^ 0.5) div 1
set i to 2
repeat until (i > limit)
if (n mod i = 0) then
repeat while (n mod i is 0)
set n to n div i
end repeat
set end of output to i
if (limit > n) then set limit to n
end if
set i to i + 1
end repeat
if (limit < n) then set end of output to n
return output
end primeFactors
on task()
script o
property sphenics : getSphenicsBelow(1000000)
end script
set {t1, t2, t3, t4, t5} to {{}, {}, count o's sphenics, 0, o's sphenics's item 200000}
repeat with i from 1 to ((count o's sphenics) - 2)
set s to o's sphenics's item i
if (s < 1000) then set end of t1 to text -4 thru -1 of (" " & s)
set s2 to o's sphenics's item (i + 2)
if (s2 - s = 2) then
if (s2 < 10000) then ¬
set end of t2 to "{" & join({s, o's sphenics's item (i + 1), s2}, ", ") & "}"
set t4 to t4 + 1
if (t4 = 5000) then ¬
set t6 to "{" & join({s, o's sphenics's item (i + 1), s2}, ", ") & "}"
end if
end repeat
set output to {"Sphenic numbers < 1,000:"}
repeat with i from 1 to 135 by 15
set end of output to join(t1's items i thru (i + 14), "")
end repeat
set end of output to linefeed & "Sphenic triplets < 10,000:"
repeat with i from 1 to 21 by 3
set end of output to join(t2's items i thru (i + 2), " ")
end repeat
set end of output to linefeed & "There are " & t3 & " sphenic numbers < 1,000,000"
set end of output to "There are " & t4 & " sphenic triplets < 1,000,000"
set end of output to "The 200,000th sphenic number is " & t5 & ¬
" (" & join(primeFactors(t5), " * ") & ")"
set end of output to "The 5,000th sphenic triplet is " & t6
return join(output, linefeed)
end task
task()
- Output:
"Sphenic numbers < 1,000:
30 42 66 70 78 102 105 110 114 130 138 154 165 170 174
182 186 190 195 222 230 231 238 246 255 258 266 273 282 285
286 290 310 318 322 345 354 357 366 370 374 385 399 402 406
410 418 426 429 430 434 435 438 442 455 465 470 474 483 494
498 506 518 530 534 555 561 574 582 590 595 598 602 606 609
610 615 618 627 638 642 645 646 651 654 658 663 665 670 678
682 705 710 715 730 741 742 754 759 762 777 782 786 790 795
805 806 814 822 826 830 834 854 861 874 885 890 894 897 902
903 906 915 935 938 942 946 957 962 969 970 978 986 987 994
Sphenic triplets < 10,000:
{1309, 1310, 1311} {1885, 1886, 1887} {2013, 2014, 2015}
{2665, 2666, 2667} {3729, 3730, 3731} {5133, 5134, 5135}
{6061, 6062, 6063} {6213, 6214, 6215} {6305, 6306, 6307}
{6477, 6478, 6479} {6853, 6854, 6855} {6985, 6986, 6987}
{7257, 7258, 7259} {7953, 7954, 7955} {8393, 8394, 8395}
{8533, 8534, 8535} {8785, 8786, 8787} {9213, 9214, 9215}
{9453, 9454, 9455} {9821, 9822, 9823} {9877, 9878, 9879}
There are 206964 sphenic numbers < 1,000,000
There are 5457 sphenic triplets < 1,000,000
The 200,000th sphenic number is 966467 (17 * 139 * 409)
The 5,000th sphenic triplet is {918005, 918006, 918007}"
J
Implementation:
sphenic=: {{ N #~ N = {{*/~.3{.y}}@q: N=. 30}.i.y }}
triplet=: {{ 0 1 2 +/~y #~ */y e.~ 0 1 2 +/ y }}
Here, sphenic gives all sphenic numbers up through its right argument, and triplet returns sequences of three adjacent numbers from its right argument.
Task examples:
9 15$sphenic 1e3
30 42 66 70 78 102 105 110 114 130 138 154 165 170 174
182 186 190 195 222 230 231 238 246 255 258 266 273 282 285
286 290 310 318 322 345 354 357 366 370 374 385 399 402 406
410 418 426 429 430 434 435 438 442 455 465 470 474 483 494
498 506 518 530 534 555 561 574 582 590 595 598 602 606 609
610 615 618 627 638 642 645 646 651 654 658 663 665 670 678
682 705 710 715 730 741 742 754 759 762 777 782 786 790 795
805 806 814 822 826 830 834 854 861 874 885 890 894 897 902
903 906 915 935 938 942 946 957 962 969 970 978 986 987 994
triplet sphenic 1e4
1309 1310 1311
1885 1886 1887
2013 2014 2015
2665 2666 2667
3729 3730 3731
5133 5134 5135
6061 6062 6063
6213 6214 6215
6305 6306 6307
6477 6478 6479
6853 6854 6855
6985 6986 6987
7257 7258 7259
7953 7954 7955
8393 8394 8395
8533 8534 8535
8785 8786 8787
9213 9214 9215
9453 9454 9455
9821 9822 9823
9877 9878 9879
# sphenic 1e6
206964
# triplet sphenic 1e6
5457
4999 { triplet sphenic 1e6 NB. 0 is first
918005 918006 918007
Phix
with javascript_semantics function get_sphenic(integer limit) sequence sphenic = {}, primes = get_primes_le(floor(limit/6)) integer pc = length(primes) for i=1 to pc-2 do for j=i+1 to pc-1 do atom prod = primes[i]*primes[j] if prod*primes[j+1]>=limit then exit end if for k=j+1 to pc do atom res = prod*primes[k] if res>=limit then exit end if sphenic &= res end for end for end for sphenic = sort(sphenic) return sphenic end function sequence sphenic = get_sphenic(1000000) printf(1,"Sphenic numbers less than 1,000:\n") printf(1,"%s\n",join_by(filter(sphenic,"<",1000),1,15," ",fmt:="%3d")) printf(1,"Sphenic triplets less than 10,000:\n") sequence triplets = {} for i=1 to length(sphenic)-2 do atom s = sphenic[i] if sphenic[i+1]==s+1 and sphenic[i+2]==s+2 then triplets = append(triplets,{s,s+1,s+2}) end if end for function tltk(sequence t) return t[3]<10000 end function printf(1,"%s\n",join_by(apply(filter(triplets,tltk),sprint),1,3," ")) printf(1,"There are %,d sphenic numbers less than 1,000,000.\n",length(sphenic)) printf(1,"There are %,d sphenic triplets less than 1,000,000.\n",length(triplets)) atom s = sphenic[200000] string f = join(prime_factors(s),"*",fmt:="%d") printf(1,"The 200,000th sphenic number is %,d (%s).\n", {s, f}) printf(1,"The 5,000th sphenic triplet is %v.\n", {triplets[5000]})
- Output:
Sphenic numbers less than 1,000:
30 42 66 70 78 102 105 110 114 130 138 154 165 170 174
182 186 190 195 222 230 231 238 246 255 258 266 273 282 285
286 290 310 318 322 345 354 357 366 370 374 385 399 402 406
410 418 426 429 430 434 435 438 442 455 465 470 474 483 494
498 506 518 530 534 555 561 574 582 590 595 598 602 606 609
610 615 618 627 638 642 645 646 651 654 658 663 665 670 678
682 705 710 715 730 741 742 754 759 762 777 782 786 790 795
805 806 814 822 826 830 834 854 861 874 885 890 894 897 902
903 906 915 935 938 942 946 957 962 969 970 978 986 987 994
Sphenic triplets less than 10,000:
{1309,1310,1311} {1885,1886,1887} {2013,2014,2015}
{2665,2666,2667} {3729,3730,3731} {5133,5134,5135}
{6061,6062,6063} {6213,6214,6215} {6305,6306,6307}
{6477,6478,6479} {6853,6854,6855} {6985,6986,6987}
{7257,7258,7259} {7953,7954,7955} {8393,8394,8395}
{8533,8534,8535} {8785,8786,8787} {9213,9214,9215}
{9453,9454,9455} {9821,9822,9823} {9877,9878,9879}
There are 206,964 sphenic numbers less than 1,000,000.
There are 5,457 sphenic triplets less than 1,000,000.
The 200,000th sphenic number is 966,467 (17*139*409).
The 5,000th sphenic triplet is {918005,918006,918007}.
Python
""" rosettacode.org task Sphenic_numbers """
from sympy import factorint
sphenics1m, sphenic_triplets1m = [], []
for i in range(3, 1_000_000):
d = factorint(i)
if len(d) == 3 and sum(d.values()) == 3:
sphenics1m.append(i)
if len(sphenics1m) > 2 and i - sphenics1m[-3] == 2 and i - sphenics1m[-2] == 1:
sphenic_triplets1m.append(i)
print('Sphenic numbers less than 1000:')
for i, n in enumerate(sphenics1m):
if n < 1000:
print(f'{n : 5}', end='\n' if (i + 1) % 15 == 0 else '')
else:
break
print('\n\nSphenic triplets less than 10_000:')
for i, n in enumerate(sphenic_triplets1m):
if n < 10_000:
print(f'({n - 2} {n - 1} {n})', end='\n' if (i + 1) % 3 == 0 else ' ')
else:
break
print('\nThere are', len(sphenics1m), 'sphenic numbers and', len(sphenic_triplets1m),
'sphenic triplets less than 1 million.')
S2HK = sphenics1m[200_000 - 1]
T5K = sphenic_triplets1m[5000 - 1]
print(f'The 200_000th sphenic number is {S2HK}, with prime factors {list(factorint(S2HK).keys())}.')
print(f'The 5000th sphenic triplet is ({T5K - 2} {T5K - 1} {T5K}).')
- Output:
Sphenic numbers less than 1000: 30 42 66 70 78 102 105 110 114 130 138 154 165 170 174 182 186 190 195 222 230 231 238 246 255 258 266 273 282 285 286 290 310 318 322 345 354 357 366 370 374 385 399 402 406 410 418 426 429 430 434 435 438 442 455 465 470 474 483 494 498 506 518 530 534 555 561 574 582 590 595 598 602 606 609 610 615 618 627 638 642 645 646 651 654 658 663 665 670 678 682 705 710 715 730 741 742 754 759 762 777 782 786 790 795 805 806 814 822 826 830 834 854 861 874 885 890 894 897 902 903 906 915 935 938 942 946 957 962 969 970 978 986 987 994 Sphenic triplets less than 10_000: (1309 1310 1311) (1885 1886 1887) (2013 2014 2015) (2665 2666 2667) (3729 3730 3731) (5133 5134 5135) (6061 6062 6063) (6213 6214 6215) (6305 6306 6307) (6477 6478 6479) (6853 6854 6855) (6985 6986 6987) (7257 7258 7259) (7953 7954 7955) (8393 8394 8395) (8533 8534 8535) (8785 8786 8787) (9213 9214 9215) (9453 9454 9455) (9821 9822 9823) (9877 9878 9879) There are 206964 sphenic numbers and 5457 sphenic triplets less than 1 million. The 200_000th sphenic number is 966467, with prime factors [17, 139, 409]. The 5000th sphenic triplet is (918005 918006 918007).
Raku
Not the most efficient algorithm, but massively parallelizable, so finishes pretty quickly.
use Prime::Factor;
use List::Divvy;
use Lingua::EN::Numbers;
my @sphenic = lazy (^Inf).hyper(:200batch).grep: { my @pf = .&prime-factors; +@pf == 3 and +@pf.unique == 3 };
my @triplets = lazy (^Inf).grep( { @sphenic[$_] + 2 == @sphenic[$_ + 2] } )\
.map: {(@sphenic[$_],@sphenic[$_+1],@sphenic[$_+2])}
say "Sphenic numbers less than 1,000:\n" ~
@sphenic.&upto(1e3).batch(15)».fmt("%3d").join: "\n";
say "\nSphenic triplets less than 10,000:";
.say for @triplets.&before(*.[2] > 1e4);
say "\nThere are {(+@sphenic.&upto(1e6)).&comma} sphenic numbers less than {1e6.Int.&comma}";
say "There are {(+@triplets.&before(*.[2] > 1e6)).&comma} sphenic triplets less than {1e6.Int.&comma}";
say "The 200,000th sphenic number is {@sphenic[2e5-1].&comma} ({@sphenic[2e5-1].&prime-factors.join(' × ')}).";
say "The 5,000th sphenic triplet is ({@triplets[5e3-1].join(', ')})."
- Output:
Sphenic numbers less than 1,000: 30 42 66 70 78 102 105 110 114 130 138 154 165 170 174 182 186 190 195 222 230 231 238 246 255 258 266 273 282 285 286 290 310 318 322 345 354 357 366 370 374 385 399 402 406 410 418 426 429 430 434 435 438 442 455 465 470 474 483 494 498 506 518 530 534 555 561 574 582 590 595 598 602 606 609 610 615 618 627 638 642 645 646 651 654 658 663 665 670 678 682 705 710 715 730 741 742 754 759 762 777 782 786 790 795 805 806 814 822 826 830 834 854 861 874 885 890 894 897 902 903 906 915 935 938 942 946 957 962 969 970 978 986 987 994 Sphenic triplets less than 10,000: (1309 1310 1311) (1885 1886 1887) (2013 2014 2015) (2665 2666 2667) (3729 3730 3731) (5133 5134 5135) (6061 6062 6063) (6213 6214 6215) (6305 6306 6307) (6477 6478 6479) (6853 6854 6855) (6985 6986 6987) (7257 7258 7259) (7953 7954 7955) (8393 8394 8395) (8533 8534 8535) (8785 8786 8787) (9213 9214 9215) (9453 9454 9455) (9821 9822 9823) (9877 9878 9879) There are 206,964 sphenic numbers less than 1,000,000 There are 5,457 sphenic triplets less than 1,000,000 The 200,000th sphenic number is 966,467 (17 × 139 × 409). The 5,000th sphenic triplet is (918005, 918006, 918007).
Wren
The approach here is to manufacture the sphenic numbers directly by first sieving for primes up to 1e6 / 6.
import "./math" for Int
import "./fmt" for Fmt
var limit = 1000000
var primes = Int.primeSieve((limit/6).floor)
var pc = primes.count
var sphenic = []
System.print("Sphenic numbers less than 1,000:")
for (i in 0...pc-2) {
for (j in i+1...pc-1) {
var prod = primes[i] * primes[j]
if (prod * primes[j + 1] >= limit) break
for (k in j+1...pc) {
var res = prod * primes[k]
if (res >= limit) break
sphenic.add(res)
}
}
}
sphenic.sort()
Fmt.tprint("$3d", sphenic.where { |s| s < 1000 }, 15)
System.print("\nSphenic triplets less than 10,000:")
var triplets = []
for (i in 0...sphenic.count-2) {
var s = sphenic[i]
if (sphenic[i+1] == s + 1 && sphenic[i+2] == s + 2) {
triplets.add([s, s + 1, s + 2])
}
}
Fmt.tprint("$18n", triplets.where { |t| t[2] < 10000 }, 3)
Fmt.print("\nThere are $,d sphenic numbers less than 1,000,000.", sphenic.count)
Fmt.print("There are $,d sphenic triplets less than 1,000,000.", triplets.count)
var s = sphenic[199999]
Fmt.print("The 200,000th sphenic number is $,d ($s).", s, Int.primeFactors(s).join("*"))
Fmt.print("The 5,000th sphenic triplet is $n.", triplets[4999])- Output:
Sphenic numbers less than 1,000: 30 42 66 70 78 102 105 110 114 130 138 154 165 170 174 182 186 190 195 222 230 231 238 246 255 258 266 273 282 285 286 290 310 318 322 345 354 357 366 370 374 385 399 402 406 410 418 426 429 430 434 435 438 442 455 465 470 474 483 494 498 506 518 530 534 555 561 574 582 590 595 598 602 606 609 610 615 618 627 638 642 645 646 651 654 658 663 665 670 678 682 705 710 715 730 741 742 754 759 762 777 782 786 790 795 805 806 814 822 826 830 834 854 861 874 885 890 894 897 902 903 906 915 935 938 942 946 957 962 969 970 978 986 987 994 Sphenic triplets less than 10,000: [1309, 1310, 1311] [1885, 1886, 1887] [2013, 2014, 2015] [2665, 2666, 2667] [3729, 3730, 3731] [5133, 5134, 5135] [6061, 6062, 6063] [6213, 6214, 6215] [6305, 6306, 6307] [6477, 6478, 6479] [6853, 6854, 6855] [6985, 6986, 6987] [7257, 7258, 7259] [7953, 7954, 7955] [8393, 8394, 8395] [8533, 8534, 8535] [8785, 8786, 8787] [9213, 9214, 9215] [9453, 9454, 9455] [9821, 9822, 9823] [9877, 9878, 9879] There are 206,964 sphenic numbers less than 1,000,000. There are 5,457 sphenic triplets less than 1,000,000. The 200,000th sphenic number is 966,467 (17*139*409). The 5,000th sphenic triplet is [918005, 918006, 918007].
XPL0
Runs in less than five seconds on Pi4.
int Factors(3);
func Sphenic(N); \Return 'true' if N is sphenic
int N, C, F, L, Q;
[L:= sqrt(N);
C:= 0; F:= 2;
loop [Q:= N/F;
if rem(0) = 0 then
[Factors(C):= F; \found a factor
C:= C+1; \count it
if C > 3 then return false;
N:= Q;
if rem(N/F) = 0 then \has a square
return false;
if F > N then quit;
]
else [F:= F+1;
if F > L then \reached limit
[Factors(C):= N;
C:= C+1;
quit;
];
];
];
return C = 3;
];
int C, N, I;
[Format(4, 0);
C:= 0; N:= 2*3*5;
Text(0, "Sphenic numbers less than 1,000:^m^j");
loop [if Sphenic(N) then
[C:= C+1;
if N < 1000 then
[RlOut(0, float(N));
if rem(C/15) = 0 then CrLf(0);
];
if C = 200_000 then
[Text(0, "The 200,000th sphenic number is ");
IntOut(0, N);
Text(0, " = ");
for I:= 0 to 2 do
[IntOut(0, Factors(I));
if I < 2 then Text(0, "*");
];
CrLf(0);
];
];
N:= N+1;
if N >= 1_000_000 then quit;
];
Text(0, "There are "); IntOut(0, C);
Text(0, " sphenic numbers less than 1,000,000^m^j^m^j");
C:= 0; N:= 2*3*5;
Text(0, "Sphenic triplets less than 10,000:^m^j");
loop [if Sphenic(N) then if Sphenic(N+1) then if Sphenic(N+2) then
[C:= C+1;
if N < 10_000 then
[ChOut(0, ^[);
for I:= 0 to 2 do
[IntOut(0, N+I);
if I < 2 then Text(0, ", ");
];
ChOut(0, ^]);
if rem(C/3) = 0 then CrLf(0) else Text(0, ", ");;
];
if C = 5000 then
[Text(0, "The 5000th sphenic triplet is [");
for I:= 0 to 2 do
[IntOut(0, N+I);
if I < 2 then Text(0, ", ");
];
Text(0, "]^m^j");
];
];
N:= N+1;
if N+2 >= 1_000_000 then quit;
];
Text(0, "There are "); IntOut(0, C);
Text(0, " sphenic triplets less than 1,000,000^m^j");
]- Output:
Sphenic numbers less than 1,000: 30 42 66 70 78 102 105 110 114 130 138 154 165 170 174 182 186 190 195 222 230 231 238 246 255 258 266 273 282 285 286 290 310 318 322 345 354 357 366 370 374 385 399 402 406 410 418 426 429 430 434 435 438 442 455 465 470 474 483 494 498 506 518 530 534 555 561 574 582 590 595 598 602 606 609 610 615 618 627 638 642 645 646 651 654 658 663 665 670 678 682 705 710 715 730 741 742 754 759 762 777 782 786 790 795 805 806 814 822 826 830 834 854 861 874 885 890 894 897 902 903 906 915 935 938 942 946 957 962 969 970 978 986 987 994 The 200,000th sphenic number is 966467 = 17*139*409 There are 206964 sphenic numbers less than 1,000,000 Sphenic triplets less than 10,000: [1309, 1310, 1311], [1885, 1886, 1887], [2013, 2014, 2015] [2665, 2666, 2667], [3729, 3730, 3731], [5133, 5134, 5135] [6061, 6062, 6063], [6213, 6214, 6215], [6305, 6306, 6307] [6477, 6478, 6479], [6853, 6854, 6855], [6985, 6986, 6987] [7257, 7258, 7259], [7953, 7954, 7955], [8393, 8394, 8395] [8533, 8534, 8535], [8785, 8786, 8787], [9213, 9214, 9215] [9453, 9454, 9455], [9821, 9822, 9823], [9877, 9878, 9879] The 5000th sphenic triplet is [918005, 918006, 918007] There are 5457 sphenic triplets less than 1,000,000