How to resolve the algorithm Pairs with common factors step by step in the Wren programming language

Published on 12 May 2024 09:40 PM
#Wren

How to resolve the algorithm Pairs with common factors step by step in the Wren programming language

Table of Contents

Problem Statement

Generate the sequence where each term n is the count of the pairs (x,y) with 1 < x < y <= n, that have at least one common prime factor.

For instance, when n = 9, examine the pairs: Find all of the pairs that have at least one common prime factor: and count them:

Terms may be found directly using the formula: where 𝚽() is Phi; the Euler totient function.

For the term a(p), if p is prime, then a(p) is equal to the previous term.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Pairs with common factors step by step in the Wren programming language

Source code in the wren programming language

import "./math" for Int
import "./fmt" for Fmt

var totient = Fn.new { |n|
    var tot = n
    var i = 2
    while (i*i <= n) {
        if (n%i == 0) {
            while(n%i == 0) n = (n/i).floor
            tot = tot - (tot/i).floor
        }
        if (i == 2) i = 1
        i = i + 2
    }
    if (n > 1) tot = tot - (tot/n).floor
    return tot
}

var max = 1e6
var a = List.filled(max, 0)
var sumPhi = 0
for (n in 1..max) {
    sumPhi = sumPhi + totient.call(n)
    if (Int.isPrime(n)) {
        a[n-1] = a[n-2]
    } else {
        a[n-1] = n * (n - 1) / 2 + 1 - sumPhi
    }
}

System.print("Number of pairs with common factors - first one hundred terms:")
Fmt.tprint("$,5d ", a[0..99], 10)
System.print()
var limits = [1, 10, 1e2, 1e3, 1e4, 1e5, 1e6]
for (limit in limits) {
    Fmt.print("The $,r term: $,d", limit, a[limit-1])
}

You may also check:How to resolve the algorithm Increment a numerical string step by step in the NetRexx programming language
You may also check:How to resolve the algorithm Terminal control/Display an extended character step by step in the Go programming language
You may also check:How to resolve the algorithm Middle three digits step by step in the Sidef programming language
You may also check:How to resolve the algorithm Fibonacci sequence step by step in the SuperCollider programming language
You may also check:How to resolve the algorithm Pick random element step by step in the Rust programming language