Radical of an integer

Radical of an integer 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.

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

• Square-free integers
• Almost prime

References

• Wikipedia article Radical of an integer
• OEIS sequence A007947: Largest square free number dividing n

Wren

Library: Wren-math

Library: Wren-seq

Library: Wren-fmt

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