Numbers which are the cube roots of the product of their proper divisors: Difference between revisions
m (→{{header|J}}) |
(→{{header|Wren}}: Despite obtaining the correct answers, the previous solution was unsafe for n > 208063.) |
||
Line 246: | Line 246: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{libheader|Wren-math}} |
{{libheader|Wren-math}} |
||
{{libheader|Wren-long}} |
|||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
<syntaxhighlight lang="ecmascript">import "./math" for Int, Nums |
<syntaxhighlight lang="ecmascript">import "./math" for Int, Nums |
||
import "./long" for ULong, ULongs |
|||
import "./fmt" for Fmt |
import "./fmt" for Fmt |
||
Line 253: | Line 255: | ||
var count = 0 |
var count = 0 |
||
var n = 1 |
var n = 1 |
||
var ln |
|||
var maxSafe = Num.maxSafeInteger.cbrt.floor |
|||
System.print("First 50 numbers which are the cube roots of the products of their proper divisors:") |
System.print("First 50 numbers which are the cube roots of the products of their proper divisors:") |
||
while (true) { |
while (true) { |
||
var pd = Int.properDivisors(n) |
var pd = Int.properDivisors(n) |
||
if (Nums.prod(pd) == n * n * n) |
if ((n <= maxSafe && Nums.prod(pd) == n * n * n) || |
||
(ULongs.prod(pd.map { |f| ULong.new(f) }) == (ln = ULong.new(n)) * ln * ln )) { |
|||
count = count + 1 |
count = count + 1 |
||
if (count <= 50) { |
if (count <= 50) { |
||
Line 266: | Line 271: | ||
Fmt.print("5,000th : $,d", n) |
Fmt.print("5,000th : $,d", n) |
||
} else if (count == 50000) { |
} else if (count == 50000) { |
||
Fmt.print("50,000th: $,d", n) |
Fmt.print("50,000th: $,d", n) |
||
break |
break |
||
} |
} |
Revision as of 17:52, 30 September 2022
- Example
Consider the number 24. Its proper divisors are: 1, 2, 3, 4, 6, 8 and 12. Their product is 13,824 and the cube root of this is 24. So 24 satisfies the definition in the task title.
- Task
Compute and show here the first 50 positive integers which are the cube roots of the product of their proper divisors.
Also show the 500th and 5,000th such numbers.
- Stretch
Compute and show the 50,000th such number.
- Reference
- Note
OEIS considers 1 to be the first number in this sequence even though, strictly speaking, it has no proper divisors. Please therefore do likewise.
ALGOL 68
Attempting the task by computing divisor products (as this sample does) requires large integers as some of the products needed are quite big. This ignores numbers where the divisor product is going to be larger than the cube of the maximum number it considers.
It constructs a table of proper divisor products to avoid factorising each number. As the J sample suggests, alternative approaches could avoid the need for large integers.
Requires an implementation of Algol 68 where LONG INT is more than 64 bits, in ALGOL 68G, LONG INT is 128 bit in version 3 and allows up to 35 digits in version 2. In order to run this under Windows (and probably other operating systems) with Algol 68G, a large heap size must be specified, e.g. with -heap 256M
on the command line.
BEGIN # find some numbers which are the cube roots of the product of their #
# proper divisors #
INT max number = 500 000; # maximum number we will consider #
# form a table of proper divisor products - assume the pdp of 1 is 1 #
LONG INT max product = LENG max number * LENG max number * LENG max number;
[ 1 : max number ]LONG INT pdp; FOR i TO UPB pdp DO pdp[ i ] := IF ODD i THEN 1 ELSE 2 FI OD;
FOR i FROM 3 TO UPB pdp DO
FOR j FROM i + i BY i TO UPB pdp DO
IF pdp[ j ] < 0 THEN
# the product has already overflowed #
SKIP
ELIF pdp[ j ] >= max product THEN
# the product will be too large to be a cube of interest #
pdp[ j ] := -1
ELSE
# the product hasn't overflowed yet #
pdp[ j ] *:= i
FI
OD
OD;
# show the numbers which are the cube root of their pdp, i.e. where #
# the pdp is the cube of the number #
INT next show := 500;
INT c count := 0;
FOR n TO UPB pdp DO
IF LONG INT n3 = LENG n * LENG n * LENG n;
n3 = pdp[ n ]
THEN
# found a suitable number #
IF ( c count +:= 1 ) <= 50 THEN
print( ( " ", whole( n, -3 ) ) );
IF c count MOD 10 = 0 THEN print( ( newline ) ) FI
ELIF c count = next show THEN
print( ( whole( c count, -9 ), "th: ", whole( n, 0 ), newline ) );
next show *:= 10
FI
FI
OD
END
- Output:
1 24 30 40 42 54 56 66 70 78 88 102 104 105 110 114 128 130 135 136 138 152 154 165 170 174 182 184 186 189 190 195 222 230 231 232 238 246 248 250 255 258 266 273 282 285 286 290 296 297 500th: 2526 5000th: 23118 50000th: 223735
C++
#include <iomanip>
#include <iostream>
unsigned int divisor_count(unsigned int n) {
unsigned int total = 1;
for (; (n & 1) == 0; n >>= 1)
++total;
for (unsigned int p = 3; p * p <= n; p += 2) {
unsigned int count = 1;
for (; n % p == 0; n /= p)
++count;
total *= count;
}
if (n > 1)
total *= 2;
return total;
}
int main() {
std::cout.imbue(std::locale(""));
std::cout << "First 50 numbers which are the cube roots of the products of "
"their proper divisors:\n";
for (unsigned int n = 1, count = 0; count < 50000; ++n) {
if (n == 1 || divisor_count(n) == 8) {
++count;
if (count <= 50)
std::cout << std::setw(3) << n
<< (count % 10 == 0 ? '\n' : ' ');
else if (count == 500 || count == 5000 || count == 50000)
std::cout << std::setw(6) << count << "th: " << n << '\n';
}
}
}
- Output:
First 50 numbers which are the cube roots of the products of their proper divisors: 1 24 30 40 42 54 56 66 70 78 88 102 104 105 110 114 128 130 135 136 138 152 154 165 170 174 182 184 186 189 190 195 222 230 231 232 238 246 248 250 255 258 266 273 282 285 286 290 296 297 500th: 2,526 5,000th: 23,118 50,000th: 223,735
J
Note that the cube root of the product of the proper divisors is the fourth root of the product of all divisors of a positive integer. That said, we do not need to find roots here -- we only need to inspect the powers of the prime factors of the number:
F=: 1 8 e.~_ */@:>:@q:"0 ]
Task examples:
N=: 1+I.F 1+i.2^18
5 10$N
1 24 30 40 42 54 56 66 70 78
88 102 104 105 110 114 128 130 135 136
138 152 154 165 170 174 182 184 186 189
190 195 222 230 231 232 238 246 248 250
255 258 266 273 282 285 286 290 296 297
499{N
2526
4999{N
23118
49999{N
223735
Phix
with javascript_semantics sequence n50 = {} integer count = 0, n = 1, n5 = 500 printf(1,"First 50 numbers which are the cube roots\n") printf(1," of the products of their proper divisors:\n") while count<50000 do if product(factors(n))=n*n*n then count += 1 if count<=50 then n50 &= n if count=50 then printf(1,"%s\n",join_by(n50,1,10,"",fmt:="%4d")) end if elsif count=n5 then printf(1,"%,6dth: %,d\n",{n5,n}) n5 *= 10 end if end if n += 1 end while
- Output:
First 50 numbers which are the cube roots of the products of their proper divisors: 1 24 30 40 42 54 56 66 70 78 88 102 104 105 110 114 128 130 135 136 138 152 154 165 170 174 182 184 186 189 190 195 222 230 231 232 238 246 248 250 255 258 266 273 282 285 286 290 296 297 500th: 2,526 5,000th: 23,118 50,000th: 223,735
Python
''' Rosetta code rosettacode.org/wiki/Numbers_which_are_the_cube_roots_of_the_product_of_their_proper_divisors '''
from functools import reduce
from sympy import divisors
FOUND = 0
for num in range(1, 1_000_000):
divprod = reduce(lambda x, y: x * y, divisors(num)[:-1])if num > 1 else 1
if num * num * num == divprod:
FOUND += 1
if FOUND <= 50:
print(f'{num:5}', end='\n' if FOUND % 10 == 0 else '')
if FOUND == 500:
print(f'\nFive hundreth: {num:,}')
if FOUND == 5000:
print(f'\nFive thousandth: {num:,}')
if FOUND == 50000:
print(f'\nFifty thousandth: {num:,}')
break
- Output:
1 24 30 40 42 54 56 66 70 78 88 102 104 105 110 114 128 130 135 136 138 152 154 165 170 174 182 184 186 189 190 195 222 230 231 232 238 246 248 250 255 258 266 273 282 285 286 290 296 297 Five hundreth: 2,526 Five thousandth: 23,118 Fifty thousandth: 223,735
Raku
use Prime::Factor;
use Lingua::EN::Numbers;
my @cube-div = lazy 1, |(2..∞).hyper.grep: { .³ == [×] .&proper-divisors }
put "First 50 numbers which are the cube roots of the products of their proper divisors:\n" ~
@cube-div[^50]».fmt("%3d").batch(10).join: "\n";
printf "\n%16s: %s\n", .Int.&ordinal.tc, comma @cube-div[$_ - 1] for 5e2, 5e3, 5e4;
- Output:
First 50 numbers which are the cube roots of the products of their proper divisors: 1 24 30 40 42 54 56 66 70 78 88 102 104 105 110 114 128 130 135 136 138 152 154 165 170 174 182 184 186 189 190 195 222 230 231 232 238 246 248 250 255 258 266 273 282 285 286 290 296 297 Five hundredth: 2,526 Five thousandth: 23,118 Fifty thousandth: 223,735
Wren
import "./math" for Int, Nums
import "./long" for ULong, ULongs
import "./fmt" for Fmt
var numbers50 = []
var count = 0
var n = 1
var ln
var maxSafe = Num.maxSafeInteger.cbrt.floor
System.print("First 50 numbers which are the cube roots of the products of their proper divisors:")
while (true) {
var pd = Int.properDivisors(n)
if ((n <= maxSafe && Nums.prod(pd) == n * n * n) ||
(ULongs.prod(pd.map { |f| ULong.new(f) }) == (ln = ULong.new(n)) * ln * ln )) {
count = count + 1
if (count <= 50) {
numbers50.add(n)
if (count == 50) Fmt.tprint("$3d", numbers50, 10)
} else if (count == 500) {
Fmt.print("\n500th : $,d", n)
} else if (count == 5000) {
Fmt.print("5,000th : $,d", n)
} else if (count == 50000) {
Fmt.print("50,000th: $,d", n)
break
}
}
n = n + 1
}
- Output:
First 50 numbers which are the cube roots of the products of their proper divisors: 1 24 30 40 42 54 56 66 70 78 88 102 104 105 110 114 128 130 135 136 138 152 154 165 170 174 182 184 186 189 190 195 222 230 231 232 238 246 248 250 255 258 266 273 282 285 286 290 296 297 500th : 2,526 5,000th : 23,118 50,000th: 223,735