Pairs with common factors: Difference between revisions
m
Minor reformatting.
(→{{header|RPL}}: HP-49+ version) |
m (Minor reformatting.) |
||
| (8 intermediate revisions by 2 users not shown) | |||
Line 282:
The 100,000th term: 1,960,299,247
The 1,000,000th term: 196,035,947,609
</pre>
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <algorithm>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>
std::vector<uint32_t> totients;
std::vector<uint32_t> primes;
void listTotients(const uint32_t& maximum) {
totients.resize(maximum + 1);
std::iota(totients.begin(), totients.end(), 0);
for ( uint32_t i = 2; i <= maximum; ++i ) {
if ( totients[i] == i ) {
totients[i] = i - 1;
for ( uint32_t j = i * 2; j <= maximum; j += i ) {
totients[j] = ( totients[j] / i ) * ( i - 1 );
}
}
}
}
void listPrimeNumbers(const uint32_t& maximum) {
const uint32_t halfMaximum = ( maximum + 1 ) / 2;
std::vector<bool> composite(halfMaximum, false);
for ( uint32_t i = 1, p = 3; i < halfMaximum; p += 2, ++i ) {
if ( ! composite[i] ) {
for ( uint32_t j = i + p; j < halfMaximum; j += p ) {
composite[j] = true;
}
}
}
primes.push_back(2);
for ( uint32_t i = 1, p = 3; i < halfMaximum; p += 2, ++i ) {
if ( ! composite[i] ) {
primes.push_back(p);
}
}
}
int main() {
const uint32_t maximum = 1'000'000;
listPrimeNumbers(maximum);
listTotients(maximum);
std::vector<uint64_t> pairsCount(maximum + 1, 0);
uint64_t totientSum = 0;
for ( uint64_t number = 1; number <= maximum; ++number ) {
totientSum += totients[number];
if ( std::binary_search(primes.begin(), primes.end(), number) ) {
pairsCount[number] = pairsCount[number - 1];
} else {
pairsCount[number] = ( number * ( number - 1 ) >> 1 ) - totientSum + 1;
}
}
std::cout << "The first one hundred terms of the number of pairs with common factors:" << std::endl;
for ( uint32_t number = 1; number <= 100; ++number ) {
std::cout << std::setw(4) << pairsCount[number] << ( ( number % 10 == 0 ) ? "\n" : " " );
}
std::cout << std::endl;
uint32_t term = 1;
while ( term <= maximum ) {
std::cout << std::left << std::setw(14)
<< "Term " + std::to_string(term) + ": " << pairsCount[term] << std::endl;
term *= 10;
}
}
</syntaxhighlight>
{{ out }}
<pre>
The first one hundred terms of the number of pairs with common factors:
0 0 0 1 1 4 4 7 9 14
14 21 21 28 34 41 41 52 52 63
71 82 82 97 101 114 122 137 137 158
158 173 185 202 212 235 235 254 268 291
291 320 320 343 363 386 386 417 423 452
470 497 497 532 546 577 597 626 626 669
669 700 726 757 773 818 818 853 877 922
922 969 969 1006 1040 1079 1095 1148 1148 1195
1221 1262 1262 1321 1341 1384 1414 1461 1461 1526
1544 1591 1623 1670 1692 1755 1755 1810 1848 1907
Term 1: 0
Term 10: 14
Term 100: 1907
Term 1000: 195309
Term 10000: 19597515
Term 100000: 1960299247
Term 1000000: 196035947609
</pre>
Line 551 ⟶ 650:
Here, <code>p.</code> calculates a polynomial (1 + (-x)/2 + (x^2)/2 in this example), <code>5&p:</code> is euler's totient function, <code>@{:</code> modifies the polynomial to only operate on the final element of a sequence, <code>+/</code> is sum and <code>+/\</code> is running sum, and <code>1+i.n</code> is the sequence of numbers 1 through n.
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public final class PairsWithCommonFactors {
public static void main(String[] args) {
final int maximum = 1_000_000;
listPrimeNumbers(maximum);
listTotients(maximum);
long[] pairsCount = new long[maximum + 1];
long totientSum = 0;
for ( int number = 1; number <= maximum; number++ ) {
totientSum += totients[number];
if ( Collections.binarySearch(primes, number) > 0 ) {
pairsCount[number] = pairsCount[number - 1];
} else {
pairsCount[number] = ( (long) number * ( number - 1 ) >> 1 ) - totientSum + 1;
}
}
System.out.println("The first one hundred terms of the number of pairs with common factors:");
for ( int number = 1; number <= 100; number++ ) {
System.out.print(String.format("%4d%s", pairsCount[number], ( ( number % 10 == 0 ) ? "\n" : " " )));
}
System.out.println();
int term = 1;
while ( term <= maximum ) {
System.out.println(String.format("%-14s%s", "Term " + term + ": ", pairsCount[term]));
term *= 10;
}
}
private static void listTotients(int maximum) {
totients = new int[maximum + 1];
for ( int i = 0; i <= maximum; i++ ) {
totients[i] = i;
}
for ( int i = 2; i <= maximum; i++ ) {
if ( totients[i] == i ) {
totients[i] = i - 1;
for ( int j = i * 2; j <= maximum; j += i ) {
totients[j] = ( totients[j] / i ) * ( i - 1 );
}
}
}
}
private static void listPrimeNumbers(int maximum) {
final int halfMaximum = ( maximum + 1 ) / 2;
boolean[] composite = new boolean[halfMaximum];
for ( int i = 1, p = 3; i < halfMaximum; p += 2, i++ ) {
if ( ! composite[i] ) {
for ( int j = i + p; j < halfMaximum; j += p ) {
composite[j] = true;
}
}
}
primes = new ArrayList<Integer>(List.of( 2 ));
for ( int i = 1, p = 3; i < halfMaximum; p += 2, i++ ) {
if ( ! composite[i] ) {
primes.add(p);
}
}
}
private static int[] totients;
private static List<Integer> primes;
}
</syntaxhighlight>
{{ out }}
<pre>
The first one hundred terms of the number of pairs with common factors:
0 0 0 1 1 4 4 7 9 14
14 21 21 28 34 41 41 52 52 63
71 82 82 97 101 114 122 137 137 158
158 173 185 202 212 235 235 254 268 291
291 320 320 343 363 386 386 417 423 452
470 497 497 532 546 577 597 626 626 669
669 700 726 757 773 818 818 853 877 922
922 969 969 1006 1040 1079 1095 1148 1148 1195
1221 1262 1262 1321 1341 1384 1414 1461 1461 1526
1544 1591 1623 1670 1692 1755 1755 1810 1848 1907
Term 1: 0
Term 10: 14
Term 100: 1907
Term 1000: 195309
Term 10000: 19597515
Term 100000: 1960299247
Term 1000000: 196035947609
</pre>
=={{header|jq}}==
Line 659 ⟶ 858:
The 1,000,000th pair with common factors count is 196,035,947,609
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
{{trans|Julia}}
<syntaxhighlight lang="mathematica">(* Define the prime counting function (pcf) *)
pcf[n_] := n (n - 1)/2 + 1 - Total[EulerPhi /@ Range[n]]
(* Print pairs of (n, pcf(n)) for n from 1 to 100 *)
Do[
Module[{pair = pcf[n], pairString},
pairString = ToString[StringPadRight[ToString[pair], 5]];
If[Mod[n, 20] == 0,
WriteString["stdout", pairString <> "\n"],
WriteString["stdout", pairString, " "]
]
],
{n, 1, 100}
]
(* Print the 10^expo-th pair with common factors count *)
Do[
Print["The ", ToString[NumberForm[10^expo, DigitBlock -> 3]],
"th pair with common factors count is ",
ToString[NumberForm[pcf[10^expo], DigitBlock -> 3]]],
{expo, 1, 6}
]</syntaxhighlight>
{{out}}
<pre>
0 0 0 1 1 4 4 7 9 14 14 21 21 28 34 41 41 52 52 63
71 82 82 97 101 114 122 137 137 158 158 173 185 202 212 235 235 254 268 291
291 320 320 343 363 386 386 417 423 452 470 497 497 532 546 577 597 626 626 669
669 700 726 757 773 818 818 853 877 922 922 969 969 1006 1040 1079 1095 1148 1148 1195
1221 1262 1262 1321 1341 1384 1414 1461 1461 1526 1544 1591 1623 1670 1692 1755 1755 1810 1848 1907
The 10th pair with common factors count is 14
The 100th pair with common factors count is 1,907
The 1,000th pair with common factors count is 195,309
The 10,000th pair with common factors count is 19,597,515
The 100,000th pair with common factors count is 1,960,299,247
The 1,000,000th pair with common factors count is 196,035,947,609
</pre>
=={{header|Maxima}}==
{{trans|Mathematica_/_Wolfram_Language}}
<syntaxhighlight lang="Maxima">/* Define the prime counting function (pcf) */
pcf(n) := n*(n - 1)/2 + 1 - sum(totient(i), i, 1, n);
/* Print pairs of (n, pcf(n)) for n from 1 to 100 */
for n:1 thru 100 do (
pcf_n : ev(pcf(n), numer),
if mod(n, 20) = 0 then (
printf(true, "~4d~%", pcf_n)
) else (
printf(true, "~4d ", pcf_n)
)
);
/* Print the 10^expo-th pair with common factors count */
for expo:1 thru 6 do (
pcf_10expo : ev(pcf(10^expo), numer),
printf(true, "The ~a-th pair with common factors count is ~a~%", 10^expo, pcf_10expo)
);</syntaxhighlight>
{{out}}
<pre>
0 0 0 1 1 4 4 7 9 14 14 21 21 28 34 41 41 52 52 63
71 82 82 97 101 114 122 137 137 158 158 173 185 202 212 235 235 254 268 291
291 320 320 343 363 386 386 417 423 452 470 497 497 532 546 577 597 626 626 669
669 700 726 757 773 818 818 853 877 922 922 969 969 1006 1040 1079 1095 1148 1148 1195
1221 1262 1262 1321 1341 1384 1414 1461 1461 1526 1544 1591 1623 1670 1692 1755 1755 1810 1848 1907
The 10-th pair with common factors count is 14
The 100-th pair with common factors count is 1907
The 1000-th pair with common factors count is 195309
The 10000-th pair with common factors count is 19597515
The 100000-th pair with common factors count is 1960299247
The 1000000-th pair with common factors count is 196035947609
</pre>
=={{header|Nim}}==
| |||