Radical of an integer: Difference between revisions
Thundergnat (talk | contribs) m (→{{header|Raku}}: Add a Raku example) |
|||
Line 28: | Line 28: | ||
* OEIS sequence [[oeis:A007947|A007947: Largest square free number dividing n]] |
* OEIS sequence [[oeis:A007947|A007947: Largest square free number dividing n]] |
||
<br> |
<br> |
||
=={{header|jq}}== |
|||
'''Adapted from [[#Wren|Wren]]''' |
|||
{{Works with|jq}} |
|||
Also works with gojq, the Go implementations of jq, |
|||
except that gojq is likely to run out of memory before completing part2. |
|||
<syntaxhighlight lang=jq> |
|||
# Utility functions |
|||
def lpad($len): tostring | ($len - length) as $l | (" " * $l) + .; |
|||
def prod(s): reduce s as $x (1; . * $x); |
|||
def sum(s): reduce s as $x (0; . + $x); |
|||
def uniq(s): |
|||
foreach s as $x (null; |
|||
if . and $x == .[0] then .[1] = false |
|||
else [$x, true] |
|||
end; |
|||
if .[1] then .[0] else empty end); |
|||
# Prime number functions |
|||
# Returns the prime factors of . in order using a wheel with basis [2, 3, 5]. |
|||
def primeFactors: |
|||
def out($i): until (.n % $i != 0; .factors += [$i] | .n = ((.n/$i)|floor) ); |
|||
if . < 2 then [] |
|||
else [4, 2, 4, 2, 4, 6, 2, 6] as $inc |
|||
| { n: ., |
|||
factors: [] } |
|||
| out(2) |
|||
| out(3) |
|||
| out(5) |
|||
| .k = 7 |
|||
| .i = 0 |
|||
| until(.k * .k > .n; |
|||
if .n % .k == 0 |
|||
then .factors += [.k] |
|||
| .n = ((.n/.k)|floor) |
|||
else .k += $inc[.i] |
|||
| .i = ((.i + 1) % 8) |
|||
end) |
|||
| if .n > 1 then .factors += [.n] else . end |
|||
| .factors |
|||
end; |
|||
# Input: a positive integer |
|||
# Output: an array, $a, of length .+1 such that |
|||
# $a[$i] is $i if $i is prime, and false otherwise. |
|||
def primeSieve: |
|||
# erase(i) sets .[i*j] to false for integral j > 1 |
|||
def erase($i): |
|||
if .[$i] then |
|||
reduce (range(2*$i; length; $i)) as $j (.; .[$j] = false) |
|||
else . |
|||
end; |
|||
(. + 1) as $n |
|||
| (($n|sqrt) / 2) as $s |
|||
| [null, null, range(2; $n)] |
|||
| reduce (2, 1 + (2 * range(1; $s))) as $i (.; erase($i)) ; |
|||
# Number of primes up to and including . |
|||
def primeCount: |
|||
sum(primeSieve[] | select(.) | 1); |
|||
## Radicals |
|||
def task1: |
|||
{ radicals: [0], |
|||
counts: [range(0;8)|0] } |
|||
| .radicals[1] = 1 |
|||
| .counts[1] = 1 |
|||
| foreach range(2; 1+1e6) as $i (.; |
|||
.factors = [uniq($i|primeFactors[])] |
|||
| (.factors|length) as $fc |
|||
| .counts[$fc] += 1 |
|||
| if $i <= 50 then .radicals[$i] = prod(.factors[]) else . end ; |
|||
if $i == 50 |
|||
then "The radicals for the first 50 positive integers are:", |
|||
(.radicals[1:] | _nwise(10) | map(lpad(4)) | join(" ")), |
|||
"" |
|||
elif $i | IN( 99999, 499999, 999999) |
|||
then "Radical for \($i|lpad(8)): \(prod(.factors[])|lpad(8))" |
|||
elif $i == 1e6 |
|||
then "\nBreakdown of numbers of distinct prime factors", |
|||
"for positive integers from 1 to 1,000,000:", |
|||
(range(1; 8) as $i |
|||
| " \($i): \(.counts[$i]|lpad(8))"), |
|||
" ---------", |
|||
" \(sum(.counts[]))" |
|||
else empty |
|||
end); |
|||
def task2: |
|||
def pad: lpad(6); |
|||
(1000|primeSieve|map(select(.))) as $primes1k |
|||
| { pcount: (1e6|primeCount), |
|||
ppcount: 0 } |
|||
| reduce $primes1k[] as $p (.; |
|||
.p2 = $p |
|||
| .done = false |
|||
| until(.done; |
|||
.p2 *= $p |
|||
| if .p2 > 1e6 then .done = true |
|||
else .ppcount += 1 |
|||
end ) ) |
|||
| "\nFor primes or powers (>1) thereof <= 1,000,000:", |
|||
" Number of primes = \(.pcount|pad)", |
|||
" Number of powers = \(.ppcount|pad)", |
|||
" Add 1 for number 1 = \(1|pad)", |
|||
" ------", |
|||
" \( (.pcount + .ppcount + 1)|pad)" ; |
|||
task1, task2 |
|||
</syntaxhighlight> |
|||
<pre> |
|||
The radicals for the first 50 positive integers are: |
|||
1 2 3 2 5 6 7 2 3 10 |
|||
11 6 13 14 15 2 17 6 19 10 |
|||
21 22 23 6 5 26 3 14 29 30 |
|||
31 2 33 34 35 6 37 38 39 10 |
|||
41 42 43 22 15 46 47 6 7 10 |
|||
Radical for 99999: 33333 |
|||
Radical for 499999: 3937 |
|||
Radical for 999999: 111111 |
|||
Breakdown of numbers of distinct prime factors |
|||
for positive integers from 1 to 1,000,000: |
|||
1: 78735 |
|||
2: 288726 |
|||
3: 379720 |
|||
4: 208034 |
|||
5: 42492 |
|||
6: 2285 |
|||
7: 8 |
|||
--------- |
|||
1000000 |
|||
For primes or powers (>1) thereof <= 1,000,000: |
|||
Number of primes = 78498 |
|||
Number of powers = 236 |
|||
Add 1 for number 1 = 1 |
|||
------ |
|||
78735 |
|||
</pre> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
Revision as of 01:53, 23 May 2023
- Definition
The radical of a positive integer is defined as the product of its distinct prime factors.
Although the integer 1 has no prime factors, its radical is regarded as 1 by convention.
- Example
The radical of 504 = 2³ x 3² x 7 is: 2 x 3 x 7 = 42.
- Task
1. Find and show on this page the radicals of the first 50 positive integers.
2. Find and show the radicals of the integers: 99999, 499999 and 999999.
3. By considering their radicals, show the distribution of the first one million positive integers by numbers of distinct prime factors (hint: the maximum number of distinct factors is 7).
- Bonus
By (preferably) using an independent method, calculate the number of primes and the number of powers of primes less than or equal to one million and hence check that your answer in 3. above for numbers with one distinct prime is correct.
- Related tasks
- References
- Wikipedia article Radical of an integer
- OEIS sequence A007947: Largest square free number dividing n
jq
Adapted from Wren
Also works with gojq, the Go implementations of jq, except that gojq is likely to run out of memory before completing part2.
# Utility functions
def lpad($len): tostring | ($len - length) as $l | (" " * $l) + .;
def prod(s): reduce s as $x (1; . * $x);
def sum(s): reduce s as $x (0; . + $x);
def uniq(s):
foreach s as $x (null;
if . and $x == .[0] then .[1] = false
else [$x, true]
end;
if .[1] then .[0] else empty end);
# Prime number functions
# Returns the prime factors of . in order using a wheel with basis [2, 3, 5].
def primeFactors:
def out($i): until (.n % $i != 0; .factors += [$i] | .n = ((.n/$i)|floor) );
if . < 2 then []
else [4, 2, 4, 2, 4, 6, 2, 6] as $inc
| { n: .,
factors: [] }
| out(2)
| out(3)
| out(5)
| .k = 7
| .i = 0
| until(.k * .k > .n;
if .n % .k == 0
then .factors += [.k]
| .n = ((.n/.k)|floor)
else .k += $inc[.i]
| .i = ((.i + 1) % 8)
end)
| if .n > 1 then .factors += [.n] else . end
| .factors
end;
# Input: a positive integer
# Output: an array, $a, of length .+1 such that
# $a[$i] is $i if $i is prime, and false otherwise.
def primeSieve:
# erase(i) sets .[i*j] to false for integral j > 1
def erase($i):
if .[$i] then
reduce (range(2*$i; length; $i)) as $j (.; .[$j] = false)
else .
end;
(. + 1) as $n
| (($n|sqrt) / 2) as $s
| [null, null, range(2; $n)]
| reduce (2, 1 + (2 * range(1; $s))) as $i (.; erase($i)) ;
# Number of primes up to and including .
def primeCount:
sum(primeSieve[] | select(.) | 1);
## Radicals
def task1:
{ radicals: [0],
counts: [range(0;8)|0] }
| .radicals[1] = 1
| .counts[1] = 1
| foreach range(2; 1+1e6) as $i (.;
.factors = [uniq($i|primeFactors[])]
| (.factors|length) as $fc
| .counts[$fc] += 1
| if $i <= 50 then .radicals[$i] = prod(.factors[]) else . end ;
if $i == 50
then "The radicals for the first 50 positive integers are:",
(.radicals[1:] | _nwise(10) | map(lpad(4)) | join(" ")),
""
elif $i | IN( 99999, 499999, 999999)
then "Radical for \($i|lpad(8)): \(prod(.factors[])|lpad(8))"
elif $i == 1e6
then "\nBreakdown of numbers of distinct prime factors",
"for positive integers from 1 to 1,000,000:",
(range(1; 8) as $i
| " \($i): \(.counts[$i]|lpad(8))"),
" ---------",
" \(sum(.counts[]))"
else empty
end);
def task2:
def pad: lpad(6);
(1000|primeSieve|map(select(.))) as $primes1k
| { pcount: (1e6|primeCount),
ppcount: 0 }
| reduce $primes1k[] as $p (.;
.p2 = $p
| .done = false
| until(.done;
.p2 *= $p
| if .p2 > 1e6 then .done = true
else .ppcount += 1
end ) )
| "\nFor primes or powers (>1) thereof <= 1,000,000:",
" Number of primes = \(.pcount|pad)",
" Number of powers = \(.ppcount|pad)",
" Add 1 for number 1 = \(1|pad)",
" ------",
" \( (.pcount + .ppcount + 1)|pad)" ;
task1, task2
The radicals for the first 50 positive integers are: 1 2 3 2 5 6 7 2 3 10 11 6 13 14 15 2 17 6 19 10 21 22 23 6 5 26 3 14 29 30 31 2 33 34 35 6 37 38 39 10 41 42 43 22 15 46 47 6 7 10 Radical for 99999: 33333 Radical for 499999: 3937 Radical for 999999: 111111 Breakdown of numbers of distinct prime factors for positive integers from 1 to 1,000,000: 1: 78735 2: 288726 3: 379720 4: 208034 5: 42492 6: 2285 7: 8 --------- 1000000 For primes or powers (>1) thereof <= 1,000,000: Number of primes = 78498 Number of powers = 236 Add 1 for number 1 = 1 ------ 78735
Raku
use Prime::Factor;
use List::Divvy;
use Lingua::EN::Numbers;
sub radical ($_) { [×] unique .&prime-factors }
say "First fifty radicals:\n" ~
(1..50).map({.&radical}).batch(10)».fmt("%2d").join: "\n";
say '';
printf "Radical for %7s => %7s\n", .&comma, comma .&radical
for 99999, 499999, 999999;
my %rad = 1 => 1;
my $limit = 1e6.Int;
%rad.push: $_ for (2..$limit).race(:1000batch).map: {(unique .&prime-factors).elems => $_};
say "\nRadical factor count breakdown, 1 through {comma $limit}:";
say .key ~ " => {comma +.value}" for sort %rad;
my @primes = (2..$limit).grep: &is-prime;
my int $powers;
@primes.&upto($limit.sqrt.floor).map: -> $p {
for (2..*) { ($p ** $_) < $limit ?? ++$powers !! last }
}
say qq:to/RADICAL/;
Up to {comma $limit}:
Primes: {comma +@primes}
Powers: $powers
Plus 1: 1
Total: {comma 1 + $powers + @primes}
RADICAL
- Output:
First fifty radicals: 1 2 3 2 5 6 7 2 3 10 11 6 13 14 15 2 17 6 19 10 21 22 23 6 5 26 3 14 29 30 31 2 33 34 35 6 37 38 39 10 41 42 43 22 15 46 47 6 7 10 Radical for 99,999 => 33,333 Radical for 499,999 => 3,937 Radical for 999,999 => 111,111 Radical factor count breakdown, 1 through 1,000,000: 1 => 78,735 2 => 288,726 3 => 379,720 4 => 208,034 5 => 42,492 6 => 2,285 7 => 8 Up to 1,000,000: Primes: 78,498 Powers: 236 Plus 1: 1 Total: 78,735
Wren
import "./math" for Int, Nums
import "./seq" for Lst
import "./fmt" for Fmt
var radicals = List.filled(51, 0)
radicals[1] = 1
var counts = List.filled(8, 0)
counts[1] = 1
for (i in 2..1e6) {
var factors = Lst.prune(Int.primeFactors(i))
var fc = factors.count
counts[fc] = counts[fc] + 1
if (i <= 50) radicals[i] = Nums.prod(factors)
if (i == 50) {
System.print("The radicals for the first 50 positive integers are:")
Fmt.tprint("$2d ", radicals.skip(1), 10)
System.print()
} else if (i == 99999 || i == 499999 || i == 999999) {
Fmt.print("Radical for $,7d: $,7d", i, Nums.prod(factors))
} else if (i == 1e6) {
System.print("\nBreakdown of numbers of distinct prime factors")
System.print("for positive integers from 1 to 1,000,000:")
for (i in 1..7) {
Fmt.print(" $d: $,8d", i, counts[i])
}
System.print(" ---------")
Fmt.print(" $,8d", Nums.sum(counts))
}
}
var pcount = Int.primeCount(1e6)
var ppcount = 0
var primes1k = Int.primeSieve(1000)
for (p in primes1k) {
var p2 = p
while (true) {
p2 = p2 * p
if (p2 > 1e6) break
ppcount = ppcount + 1
}
}
System.print("\nFor primes or powers (>1) thereof <= 1,000,000:")
Fmt.print(" Number of primes = $,6d", pcount)
Fmt.print(" Number of powers = $,6d", ppcount)
Fmt.print(" Add 1 for number 1 = $,6d", 1)
System.print(" ------")
Fmt.print(" $,6d", pcount + ppcount + 1)
- Output:
The radicals for the first 50 positive integers are: 1 2 3 2 5 6 7 2 3 10 11 6 13 14 15 2 17 6 19 10 21 22 23 6 5 26 3 14 29 30 31 2 33 34 35 6 37 38 39 10 41 42 43 22 15 46 47 6 7 10 Radical for 99,999: 33,333 Radical for 499,999: 3,937 Radical for 999,999: 111,111 Breakdown of numbers of distinct prime factors for positive integers from 1 to 1,000,000: 1: 78,735 2: 288,726 3: 379,720 4: 208,034 5: 42,492 6: 2,285 7: 8 --------- 1,000,000 For primes or powers (>1) thereof <= 1,000,000: Number of primes = 78,498 Number of powers = 236 Add 1 for number 1 = 1 ------ 78,735