Isqrt (integer square root) of X
From Rosetta Code
You are encouraged to solve this task according to the task description, using any language you may know.
Sometimes a function is needed to find the integer square root of X, where X can be a real non─negative number.
Often X is actually a non─negative integer.
For the purposes of this task, X can be an integer or a real number, but if it simplifies things in your computer programming language, assume it's an integer.
One of the most common uses of Isqrt is in the division of an integer by all factors (or
primes) up to the
√ X of that
integer, either to find the factors of that integer, or to determine primality.
An alternative method for finding the Isqrt of a number is to
calculate: floor( sqrt(X) )
- where sqrt is the square root function for non─negative real numbers, and
- where floor is the floor function for real numbers.
If the hardware supports the computation of (real) square roots, the above method might be a faster method for
small numbers that don't have very many significant (decimal) digits.
However, floating point arithmetic is limited in the number of (binary or decimal) digits that it can support.
- Pseudo─code using quadratic residue
For this task, the integer square root of a non─negative number will be computed using a version of quadratic residue, which has the advantage that no floating point calculations are used, only integer arithmetic. Furthermore, the divisions and multiplication can be performed by bit shifting.
The disadvantage is the limitation of the size of the largest integer that a particular computer programming language can support.
Pseudo─code of a procedure for finding the integer square root of X (all variables are integers):
q ◄── 1 /*initialize Q to unity. */
/*find a power of 4 that's greater than X.*/
perform while q <= x /*perform while Q <= X. */
q ◄── q * 4 /*multiply Q by four. */
end /*perform*/
/*Q is now greater than X.*/
z ◄── x /*set Z to the value of X.*/
r ◄── 0 /*initialize R to zero. */
perform while q > 1 /*perform while Q > unity. */
q ◄── q ÷ 4 /*integer divide by four. */
t ◄── z - r - q /*compute value of T. */
r ◄── r ÷ 2 /*integer divide by two. */
if t >= 0 then do
z ◄── t /*set Z to value of T. */
r ◄── r + q /*compute new value of R. */
end
end /*perform*/
/*R is now the Isqrt(X). */
Another version for the (above) 1st perform is:
perform until q > X /*perform until Q > X. */
q ◄── q * 4 /*multiply Q by four. */
end /*perform*/
Integer square roots of some values:
Isqrt( 0) is 0 Isqrt(60) is 7 Isqrt( 99) is 9 Isqrt( 1) is 1 Isqrt(61) is 7 Isqrt(100) is 10 Isqrt( 2) is 1 Isqrt(62) is 7 Isqrt(102) is 10 Isqrt( 3) is 1 Isqrt(63) is 7 Isqrt( 4) is 2 Isqrt(64) is 8 Isqet(120) is 10 Isqrt( 5) is 2 Isqrt(65) is 8 Isqrt(121) is 11 Isqrt( 6) is 2 Isqrt(66) is 8 Isqrt(122) is 11 Isqrt( 7) is 2 Isqrt(67) is 8 Isqrt( 8) is 2 Isqrt(68) is 8 Isqrt(143) is 11 Isqrt( 9) is 3 Isqrt(69) is 8 Isqrt(144) is 12 Isqrt(10) is 3 Isqrt(70) is 8 Isqrt(145) is 12
- Task
Compute and show all output here (on this page) for:
- the
Isqrtof the integers from 0 ───► 65 (inclusive), shown in a horizontal format. - the
Isqrtof the odd powers from 71 ───► 773 (inclusive), shown in a vertical format. - use commas in the displaying of larger numbers.
- the
You can show more numbers for the 2nd requirement if the displays fits on one screen on Rosetta Code.
If your computer programming language only supports smaller integers, show what you can.
- Related tasks
Contents
ALGOL 68[edit]
Implements the task pseudo-code.
BEGIN # Integer square roots #
PR precision 200 PR
# returns the integer square root of x; x must be >= 0 #
PROC isqrt = ( LONG LONG INT x )LONG LONG INT:
IF x < 0 THEN print( ( "Negative number in isqrt", newline ) );stop
ELIF x < 2 THEN x
ELSE
# x is greater than 1 #
# find a power of 4 that's greater than x #
LONG LONG INT q := 1;
WHILE q <= x DO q *:= 4 OD;
# find the root #
LONG LONG INT z := x;
LONG LONG INT r := 0;
WHILE q > 1 DO
q OVERAB 4;
LONG LONG INT t = z - r - q;
r OVERAB 2;
IF t >= 0 THEN
z := t;
r +:= q
FI
OD;
r
FI; # isqrt #
# returns a string representation of n with commas #
PROC commatise = ( LONG LONG INT n )STRING:
BEGIN
STRING result := "";
STRING unformatted = whole( n, 0 );
INT ch count := 0;
FOR c FROM UPB unformatted BY -1 TO LWB unformatted DO
IF ch count <= 2 THEN ch count +:= 1
ELSE ch count := 1; "," +=: result
FI;
unformatted[ c ] +=: result
OD;
result
END; # commatise #
# left-pads a string to at least n characters #
PROC pad left = ( STRING s, INT n )STRING:
BEGIN
STRING result := s;
WHILE ( UPB result - LWB result ) + 1 < n DO " " +=: result OD;
result
END; # pad left #
# task test cases #
print( ( "Integer square roots of 0..65", newline ) );
FOR i FROM 0 TO 65 DO print( ( " ", whole( isqrt( i ), 0 ) ) ) OD;
print( ( newline ) );
# integer square roots of odd powers of 7 #
print( ( "Integer square roots of 7^n", newline ) );
print( ( " n|", pad left( "7^n", 82 ), "|", pad left( "isqrt(7^n)", 42 ), newline ) );
LONG LONG INT p7 := 7;
FOR p BY 2 TO 73 DO
print( ( whole( p, -2 )
, "|"
, pad left( commatise( p7 ), 82 )
, "|"
, pad left( commatise( isqrt( p7 ) ), 42 )
, newline
)
);
p7 *:= 49
OD
END
- Output:
Integer square roots of 0..65 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 Integer square roots of 7^n n| 7^n| isqrt(7^n) 1| 7| 2 3| 343| 18 5| 16,807| 129 7| 823,543| 907 9| 40,353,607| 6,352 11| 1,977,326,743| 44,467 13| 96,889,010,407| 311,269 15| 4,747,561,509,943| 2,178,889 17| 232,630,513,987,207| 15,252,229 19| 11,398,895,185,373,143| 106,765,608 21| 558,545,864,083,284,007| 747,359,260 23| 27,368,747,340,080,916,343| 5,231,514,822 25| 1,341,068,619,663,964,900,807| 36,620,603,758 27| 65,712,362,363,534,280,139,543| 256,344,226,312 29| 3,219,905,755,813,179,726,837,607| 1,794,409,584,184 31| 157,775,382,034,845,806,615,042,743| 12,560,867,089,291 33| 7,730,993,719,707,444,524,137,094,407| 87,926,069,625,040 35| 378,818,692,265,664,781,682,717,625,943| 615,482,487,375,282 37| 18,562,115,921,017,574,302,453,163,671,207| 4,308,377,411,626,977 39| 909,543,680,129,861,140,820,205,019,889,143| 30,158,641,881,388,842 41| 44,567,640,326,363,195,900,190,045,974,568,007| 211,110,493,169,721,897 43| 2,183,814,375,991,796,599,109,312,252,753,832,343| 1,477,773,452,188,053,281 45| 107,006,904,423,598,033,356,356,300,384,937,784,807| 10,344,414,165,316,372,973 47| 5,243,338,316,756,303,634,461,458,718,861,951,455,543| 72,410,899,157,214,610,812 49| 256,923,577,521,058,878,088,611,477,224,235,621,321,607| 506,876,294,100,502,275,687 51| 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743| 3,548,134,058,703,515,929,815 53| 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407| 24,836,938,410,924,611,508,707 55| 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943| 173,858,568,876,472,280,560,953 57| 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207| 1,217,009,982,135,305,963,926,677 59| 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143| 8,519,069,874,947,141,747,486,745 61| 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007| 59,633,489,124,629,992,232,407,216 63| 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343| 417,434,423,872,409,945,626,850,517 65| 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807| 2,922,040,967,106,869,619,387,953,625 67| 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543| 20,454,286,769,748,087,335,715,675,381 69| 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607| 143,180,007,388,236,611,350,009,727,669 71| 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743| 1,002,260,051,717,656,279,450,068,093,686 73|49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407| 7,015,820,362,023,593,956,150,476,655,802
C++[edit]
#include <iomanip>
#include <iostream>
#include <sstream>
#include <boost/multiprecision/cpp_int.hpp>
using big_int = boost::multiprecision::cpp_int;
template <typename integer>
integer isqrt(integer x) {
integer q = 1;
while (q <= x)
q <<= 2;
integer r = 0;
while (q > 1) {
q >>= 2;
integer t = x - r - q;
r >>= 1;
if (t >= 0) {
x = t;
r += q;
}
}
return r;
}
std::string commatize(const big_int& n) {
std::ostringstream out;
out << n;
std::string str(out.str());
std::string result;
size_t digits = str.size();
result.reserve(4 * digits/3);
for (size_t i = 0; i < digits; ++i) {
if (i > 0 && i % 3 == digits % 3)
result += ',';
result += str[i];
}
return result;
}
int main() {
std::cout << "Integer square root for numbers 0 to 65:\n";
for (int n = 0; n <= 65; ++n)
std::cout << isqrt(n) << ' ';
std::cout << "\n\n";
std::cout << "Integer square roots of odd powers of 7 from 1 to 73:\n";
const int power_width = 83, isqrt_width = 42;
std::cout << " n |"
<< std::setw(power_width) << "7 ^ n" << " |"
<< std::setw(isqrt_width) << "isqrt(7 ^ n)"
<< '\n';
std::cout << std::string(6 + power_width + isqrt_width, '-') << '\n';
big_int p = 7;
for (int n = 1; n <= 73; n += 2, p *= 49) {
std::cout << std::setw(2) << n << " |"
<< std::setw(power_width) << commatize(p) << " |"
<< std::setw(isqrt_width) << commatize(isqrt(p))
<< '\n';
}
return 0;
}
- Output:
Integer square root for numbers 0 to 65: 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 Integer square roots of odd powers of 7 from 1 to 73: n | 7 ^ n | isqrt(7 ^ n) ----------------------------------------------------------------------------------------------------------------------------------- 1 | 7 | 2 3 | 343 | 18 5 | 16,807 | 129 7 | 823,543 | 907 9 | 40,353,607 | 6,352 11 | 1,977,326,743 | 44,467 13 | 96,889,010,407 | 311,269 15 | 4,747,561,509,943 | 2,178,889 17 | 232,630,513,987,207 | 15,252,229 19 | 11,398,895,185,373,143 | 106,765,608 21 | 558,545,864,083,284,007 | 747,359,260 23 | 27,368,747,340,080,916,343 | 5,231,514,822 25 | 1,341,068,619,663,964,900,807 | 36,620,603,758 27 | 65,712,362,363,534,280,139,543 | 256,344,226,312 29 | 3,219,905,755,813,179,726,837,607 | 1,794,409,584,184 31 | 157,775,382,034,845,806,615,042,743 | 12,560,867,089,291 33 | 7,730,993,719,707,444,524,137,094,407 | 87,926,069,625,040 35 | 378,818,692,265,664,781,682,717,625,943 | 615,482,487,375,282 37 | 18,562,115,921,017,574,302,453,163,671,207 | 4,308,377,411,626,977 39 | 909,543,680,129,861,140,820,205,019,889,143 | 30,158,641,881,388,842 41 | 44,567,640,326,363,195,900,190,045,974,568,007 | 211,110,493,169,721,897 43 | 2,183,814,375,991,796,599,109,312,252,753,832,343 | 1,477,773,452,188,053,281 45 | 107,006,904,423,598,033,356,356,300,384,937,784,807 | 10,344,414,165,316,372,973 47 | 5,243,338,316,756,303,634,461,458,718,861,951,455,543 | 72,410,899,157,214,610,812 49 | 256,923,577,521,058,878,088,611,477,224,235,621,321,607 | 506,876,294,100,502,275,687 51 | 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 | 3,548,134,058,703,515,929,815 53 | 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 | 24,836,938,410,924,611,508,707 55 | 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 | 173,858,568,876,472,280,560,953 57 | 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 | 1,217,009,982,135,305,963,926,677 59 | 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 | 8,519,069,874,947,141,747,486,745 61 | 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 | 59,633,489,124,629,992,232,407,216 63 | 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 | 417,434,423,872,409,945,626,850,517 65 | 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 | 2,922,040,967,106,869,619,387,953,625 67 | 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 | 20,454,286,769,748,087,335,715,675,381 69 | 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 | 143,180,007,388,236,611,350,009,727,669 71 | 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 | 1,002,260,051,717,656,279,450,068,093,686 73 | 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 | 7,015,820,362,023,593,956,150,476,655,802
C#[edit]
using System;
using static System.Console;
using BI = System.Numerics.BigInteger;
class Program {
static BI isqrt(BI x) { BI q = 1, r = 0, t; while (q <= x) q <<= 2; while (q > 1) {
q >>= 2; t = x - r - q; r >>= 1; if (t >= 0) { x = t; r += q; } } return r; }
static void Main() { const int max = 73, smax = 65;
int power_width = ((BI.Pow(7, max).ToString().Length / 3) << 2) + 3,
isqrt_width = (power_width + 1) >> 1;
WriteLine("Integer square root for numbers 0 to {0}:", smax);
for (int n = 0; n <= smax; ++n) Write("{0} ",
(n / 10).ToString().Replace("0", " ")); WriteLine();
for (int n = 0; n <= smax; ++n) Write("{0} ", n % 10); WriteLine();
WriteLine(new String('-', (smax << 1) + 1));
for (int n = 0; n <= smax; ++n) Write("{0} ", isqrt(n));
WriteLine("\n\nInteger square roots of odd powers of 7 from 1 to {0}:", max);
string s = string.Format("[0,2] |[1,{0}:n0] |[2,{1}:n0]",
power_width, isqrt_width).Replace("[", "{").Replace("]", "}");
WriteLine(s, "n", "7 ^ n", "isqrt(7 ^ n)");
WriteLine(new String('-', power_width + isqrt_width + 6));
BI p = 7; for (int n = 1; n <= max; n += 2, p *= 49)
WriteLine (s, n, p, isqrt(p)); }
}
- Output:
Integer square root for numbers 0 to 65:
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
-----------------------------------------------------------------------------------------------------------------------------------
0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8
Integer square roots of odd powers of 7 from 1 to 73:
n | 7 ^ n | isqrt(7 ^ n)
-----------------------------------------------------------------------------------------------------------------------------------
1 | 7 | 2
3 | 343 | 18
5 | 16,807 | 129
7 | 823,543 | 907
9 | 40,353,607 | 6,352
11 | 1,977,326,743 | 44,467
13 | 96,889,010,407 | 311,269
15 | 4,747,561,509,943 | 2,178,889
17 | 232,630,513,987,207 | 15,252,229
19 | 11,398,895,185,373,143 | 106,765,608
21 | 558,545,864,083,284,007 | 747,359,260
23 | 27,368,747,340,080,916,343 | 5,231,514,822
25 | 1,341,068,619,663,964,900,807 | 36,620,603,758
27 | 65,712,362,363,534,280,139,543 | 256,344,226,312
29 | 3,219,905,755,813,179,726,837,607 | 1,794,409,584,184
31 | 157,775,382,034,845,806,615,042,743 | 12,560,867,089,291
33 | 7,730,993,719,707,444,524,137,094,407 | 87,926,069,625,040
35 | 378,818,692,265,664,781,682,717,625,943 | 615,482,487,375,282
37 | 18,562,115,921,017,574,302,453,163,671,207 | 4,308,377,411,626,977
39 | 909,543,680,129,861,140,820,205,019,889,143 | 30,158,641,881,388,842
41 | 44,567,640,326,363,195,900,190,045,974,568,007 | 211,110,493,169,721,897
43 | 2,183,814,375,991,796,599,109,312,252,753,832,343 | 1,477,773,452,188,053,281
45 | 107,006,904,423,598,033,356,356,300,384,937,784,807 | 10,344,414,165,316,372,973
47 | 5,243,338,316,756,303,634,461,458,718,861,951,455,543 | 72,410,899,157,214,610,812
49 | 256,923,577,521,058,878,088,611,477,224,235,621,321,607 | 506,876,294,100,502,275,687
51 | 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 | 3,548,134,058,703,515,929,815
53 | 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 | 24,836,938,410,924,611,508,707
55 | 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 | 173,858,568,876,472,280,560,953
57 | 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 | 1,217,009,982,135,305,963,926,677
59 | 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 | 8,519,069,874,947,141,747,486,745
61 | 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 | 59,633,489,124,629,992,232,407,216
63 | 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 | 417,434,423,872,409,945,626,850,517
65 | 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 | 2,922,040,967,106,869,619,387,953,625
67 | 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 | 20,454,286,769,748,087,335,715,675,381
69 | 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 | 143,180,007,388,236,611,350,009,727,669
71 | 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 | 1,002,260,051,717,656,279,450,068,093,686
73 | 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 | 7,015,820,362,023,593,956,150,476,655,802
Delphi[edit]
See #Pascal.
F#[edit]
// Find Integer Floor sqrt of a Large Integer. Nigel Galloway: July 17th., 2020
let Isqrt n=let rec fN i g l=match(l>0I,i-g-l) with
(true,e) when e>=0I->fN e (g/2I+l) (l/4I)
|(true,_) ->fN i (g/2I) (l/4I)
|_ ->g
fN n 0I (let rec fG g=if g>n then g/4I else fG (g*4I) in fG 1I)
[0I..65I]|>Seq.iter(Isqrt>>string>>printf "%s "); printfn "\n"
let fN n=7I**n in [1..2..73]|>Seq.iter(fN>>Isqrt>>printfn "%a" (fun n g -> n.Write("{0:#,#}", g)))
- Output:
0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 2 18 129 907 6,352 44,467 311,269 2,178,889 15,252,229 106,765,608 747,359,260 5,231,514,822 36,620,603,758 256,344,226,312 1,794,409,584,184 12,560,867,089,291 87,926,069,625,040 615,482,487,375,282 4,308,377,411,626,977 30,158,641,881,388,842 211,110,493,169,721,897 1,477,773,452,188,053,281 10,344,414,165,316,372,973 72,410,899,157,214,610,812 506,876,294,100,502,275,687 3,548,134,058,703,515,929,815 24,836,938,410,924,611,508,707 173,858,568,876,472,280,560,953 1,217,009,982,135,305,963,926,677 8,519,069,874,947,141,747,486,745 59,633,489,124,629,992,232,407,216 417,434,423,872,409,945,626,850,517 2,922,040,967,106,869,619,387,953,625 20,454,286,769,748,087,335,715,675,381 143,180,007,388,236,611,350,009,727,669 1,002,260,051,717,656,279,450,068,093,686 7,015,820,362,023,593,956,150,476,655,802
Factor[edit]
The isqrt word is a straightforward translation of the pseudocode from the task description using lexical variables.
USING: formatting io kernel locals math math.functions
math.ranges prettyprint sequences tools.memory.private ;
:: isqrt ( x -- n )
1 :> q!
[ q x > ] [ q 4 * q! ] until
x 0 :> ( z! r! )
[ q 1 > ] [
q 4 /i q!
z r - q - :> t
r -1 shift r!
t 0 >= [
t z!
r q + r!
] when
] while
r ;
"Integer square root for numbers 0 to 65 (inclusive):" print
66 <iota> [ bl ] [ isqrt pprint ] interleave nl nl
: align ( str str str -- ) "%2s%85s%44s\n" printf ;
: show ( n -- ) dup 7 swap ^ dup isqrt [ commas ] [email protected] align ;
"x" "7^x" "isqrt(7^x)" align
"-" "---" "----------" align
1 73 2 <range> [ show ] each
- Output:
Integer square root for numbers 0 to 65 (inclusive): 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 x 7^x isqrt(7^x) - --- ---------- 1 7 2 3 343 18 5 16,807 129 7 823,543 907 9 40,353,607 6,352 11 1,977,326,743 44,467 13 96,889,010,407 311,269 15 4,747,561,509,943 2,178,889 17 232,630,513,987,207 15,252,229 19 11,398,895,185,373,143 106,765,608 21 558,545,864,083,284,007 747,359,260 23 27,368,747,340,080,916,343 5,231,514,822 25 1,341,068,619,663,964,900,807 36,620,603,758 27 65,712,362,363,534,280,139,543 256,344,226,312 29 3,219,905,755,813,179,726,837,607 1,794,409,584,184 31 157,775,382,034,845,806,615,042,743 12,560,867,089,291 33 7,730,993,719,707,444,524,137,094,407 87,926,069,625,040 35 378,818,692,265,664,781,682,717,625,943 615,482,487,375,282 37 18,562,115,921,017,574,302,453,163,671,207 4,308,377,411,626,977 39 909,543,680,129,861,140,820,205,019,889,143 30,158,641,881,388,842 41 44,567,640,326,363,195,900,190,045,974,568,007 211,110,493,169,721,897 43 2,183,814,375,991,796,599,109,312,252,753,832,343 1,477,773,452,188,053,281 45 107,006,904,423,598,033,356,356,300,384,937,784,807 10,344,414,165,316,372,973 47 5,243,338,316,756,303,634,461,458,718,861,951,455,543 72,410,899,157,214,610,812 49 256,923,577,521,058,878,088,611,477,224,235,621,321,607 506,876,294,100,502,275,687 51 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 3,548,134,058,703,515,929,815 53 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 24,836,938,410,924,611,508,707 55 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 173,858,568,876,472,280,560,953 57 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 1,217,009,982,135,305,963,926,677 59 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 8,519,069,874,947,141,747,486,745 61 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 59,633,489,124,629,992,232,407,216 63 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 417,434,423,872,409,945,626,850,517 65 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 2,922,040,967,106,869,619,387,953,625 67 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 20,454,286,769,748,087,335,715,675,381 69 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 143,180,007,388,236,611,350,009,727,669 71 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686 73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802
Go[edit]
Go's big.Int type already has a built-in integer square root function but, as the point of this task appears to be to compute it using a particular algorithm, we re-code it from the pseudo-code given in the task description.
package main
import (
"fmt"
"log"
"math/big"
)
var zero = big.NewInt(0)
var one = big.NewInt(1)
func isqrt(x *big.Int) *big.Int {
if x.Cmp(zero) < 0 {
log.Fatal("Argument cannot be negative.")
}
q := big.NewInt(1)
for q.Cmp(x) <= 0 {
q.Lsh(q, 2)
}
z := new(big.Int).Set(x)
r := big.NewInt(0)
for q.Cmp(one) > 0 {
q.Rsh(q, 2)
t := new(big.Int)
t.Add(t, z)
t.Sub(t, r)
t.Sub(t, q)
r.Rsh(r, 1)
if t.Cmp(zero) >= 0 {
z.Set(t)
r.Add(r, q)
}
}
return r
}
func commatize(s string) string {
le := len(s)
for i := le - 3; i >= 1; i -= 3 {
s = s[0:i] + "," + s[i:]
}
return s
}
func main() {
fmt.Println("The integer square roots of integers from 0 to 65 are:")
for i := int64(0); i <= 65; i++ {
fmt.Printf("%d ", isqrt(big.NewInt(i)))
}
fmt.Println()
fmt.Println("\nThe integer square roots of powers of 7 from 7^1 up to 7^73 are:\n")
fmt.Println("power 7 ^ power integer square root")
fmt.Println("----- --------------------------------------------------------------------------------- -----------------------------------------")
pow7 := big.NewInt(7)
bi49 := big.NewInt(49)
for i := 1; i <= 73; i += 2 {
fmt.Printf("%2d %84s %41s\n", i, commatize(pow7.String()), commatize(isqrt(pow7).String()))
pow7.Mul(pow7, bi49)
}
}
- Output:
The integer square roots of integers from 0 to 65 are: 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 The integer square roots of powers of 7 from 7^1 up to 7^73 are: power 7 ^ power integer square root ----- --------------------------------------------------------------------------------- ----------------------------------------- 1 7 2 3 343 18 5 16,807 129 7 823,543 907 9 40,353,607 6,352 11 1,977,326,743 44,467 13 96,889,010,407 311,269 15 4,747,561,509,943 2,178,889 17 232,630,513,987,207 15,252,229 19 11,398,895,185,373,143 106,765,608 21 558,545,864,083,284,007 747,359,260 23 27,368,747,340,080,916,343 5,231,514,822 25 1,341,068,619,663,964,900,807 36,620,603,758 27 65,712,362,363,534,280,139,543 256,344,226,312 29 3,219,905,755,813,179,726,837,607 1,794,409,584,184 31 157,775,382,034,845,806,615,042,743 12,560,867,089,291 33 7,730,993,719,707,444,524,137,094,407 87,926,069,625,040 35 378,818,692,265,664,781,682,717,625,943 615,482,487,375,282 37 18,562,115,921,017,574,302,453,163,671,207 4,308,377,411,626,977 39 909,543,680,129,861,140,820,205,019,889,143 30,158,641,881,388,842 41 44,567,640,326,363,195,900,190,045,974,568,007 211,110,493,169,721,897 43 2,183,814,375,991,796,599,109,312,252,753,832,343 1,477,773,452,188,053,281 45 107,006,904,423,598,033,356,356,300,384,937,784,807 10,344,414,165,316,372,973 47 5,243,338,316,756,303,634,461,458,718,861,951,455,543 72,410,899,157,214,610,812 49 256,923,577,521,058,878,088,611,477,224,235,621,321,607 506,876,294,100,502,275,687 51 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 3,548,134,058,703,515,929,815 53 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 24,836,938,410,924,611,508,707 55 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 173,858,568,876,472,280,560,953 57 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 1,217,009,982,135,305,963,926,677 59 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 8,519,069,874,947,141,747,486,745 61 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 59,633,489,124,629,992,232,407,216 63 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 417,434,423,872,409,945,626,850,517 65 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 2,922,040,967,106,869,619,387,953,625 67 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 20,454,286,769,748,087,335,715,675,381 69 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 143,180,007,388,236,611,350,009,727,669 71 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686 73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802
Julia[edit]
Julia also has a built in isqrt() function which works on integer types, but the function integer_sqrt is shown for the task.
using Formatting
function integer_sqrt(x)
@assert(x >= 0)
q = one(x)
while q <= x
q <<= 2
end
z, r = x, zero(x)
while q > 1
q >>= 2
t = z - r - q
r >>= 1
if t >= 0
z = t
r += q
end
end
return r
end
println("The integer square roots of integers from 0 to 65 are:")
println(integer_sqrt.(collect(0:65)))
println("\nThe integer square roots of odd powers of 7 from 7^1 up to 7^73 are:\n")
println("power", " "^36, "7 ^ power", " "^60, "integer square root")
println("----- ", "-"^80, " ------------------------------------------")
pow7 = big"7"
for i in 1:2:73
println(lpad(i, 2), lpad(format(pow7^i, commas=true), 84),
lpad(format(integer_sqrt(pow7^i), commas=true), 43))
end
- Output:
The integer square roots of integers from 0 to 65 are: [0, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8] The integer square roots of odd powers of 7 from 7^1 up to 7^73 are: power 7 ^ power integer square root ----- -------------------------------------------------------------------------------- ------------------------------------------ 1 7 2 3 343 18 5 16,807 129 7 823,543 907 9 40,353,607 6,352 11 1,977,326,743 44,467 13 96,889,010,407 311,269 15 4,747,561,509,943 2,178,889 17 232,630,513,987,207 15,252,229 19 11,398,895,185,373,143 106,765,608 21 558,545,864,083,284,007 747,359,260 23 27,368,747,340,080,916,343 5,231,514,822 25 1,341,068,619,663,964,900,807 36,620,603,758 27 65,712,362,363,534,280,139,543 256,344,226,312 29 3,219,905,755,813,179,726,837,607 1,794,409,584,184 31 157,775,382,034,845,806,615,042,743 12,560,867,089,291 33 7,730,993,719,707,444,524,137,094,407 87,926,069,625,040 35 378,818,692,265,664,781,682,717,625,943 615,482,487,375,282 37 18,562,115,921,017,574,302,453,163,671,207 4,308,377,411,626,977 39 909,543,680,129,861,140,820,205,019,889,143 30,158,641,881,388,842 41 44,567,640,326,363,195,900,190,045,974,568,007 211,110,493,169,721,897 43 2,183,814,375,991,796,599,109,312,252,753,832,343 1,477,773,452,188,053,281 45 107,006,904,423,598,033,356,356,300,384,937,784,807 10,344,414,165,316,372,973 47 5,243,338,316,756,303,634,461,458,718,861,951,455,543 72,410,899,157,214,610,812 49 256,923,577,521,058,878,088,611,477,224,235,621,321,607 506,876,294,100,502,275,687 51 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 3,548,134,058,703,515,929,815 53 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 24,836,938,410,924,611,508,707 55 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 173,858,568,876,472,280,560,953 57 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 1,217,009,982,135,305,963,926,677 59 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 8,519,069,874,947,141,747,486,745 61 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 59,633,489,124,629,992,232,407,216 63 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 417,434,423,872,409,945,626,850,517 65 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 2,922,040,967,106,869,619,387,953,625 67 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 20,454,286,769,748,087,335,715,675,381 69 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 143,180,007,388,236,611,350,009,727,669 71 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686 73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802
Pascal[edit]
[1]
//************************************************//
// //
// Thanks for rvelthuis for BigIntegers library //
// https://github.com/rvelthuis/DelphiBigNumbers //
// //
//************************************************//
program IsqrtTask;
{$APPTYPE CONSOLE}
{$R *.res}
uses
System.SysUtils,
Velthuis.BigIntegers;
function isqrt(x: BigInteger): BigInteger;
var
q, r, t: BigInteger;
begin
q := 1;
r := 0;
while (q <= x) do
q := q shl 2;
while (q > 1) do
begin
q := q shr 2;
t := x - r - q;
r := r shr 1;
if (t >= 0) then
begin
x := t;
r := r + q;
end;
end;
Result := r;
end;
function commatize(const n: BigInteger; size: Integer): string;
var
str: string;
digits: Integer;
i: Integer;
begin
Result := '';
str := n.ToString;
digits := str.Length;
for i := 1 to digits do
begin
if ((i > 1) and (((i - 1) mod 3) = (digits mod 3))) then
Result := Result + ',';
Result := Result + str[i];
end;
if Result.Length < size then
Result := string.Create(' ', size - Result.Length) + Result;
end;
const
POWER_WIDTH = 83;
ISQRT_WIDTH = 42;
var
n, i: Integer;
f: TextFile;
p: BigInteger;
begin
AssignFile(f, 'output.txt');
rewrite(f);
Writeln(f, 'Integer square root for numbers 0 to 65:');
for n := 0 to 65 do
Write(f, isqrt(n).ToString, ' ');
Writeln(f, #10#10'Integer square roots of odd powers of 7 from 1 to 73:');
Write(f, ' n |', string.Create(' ', 78), '7 ^ n |', string.Create(' ', 30),
'isqrt(7 ^ n)'#10);
Writeln(f, string.Create('-', 17 + POWER_WIDTH + ISQRT_WIDTH));
p := 7;
n := 1;
repeat
Writeln(f, Format('%2d', [n]), ' |', commatize(p, power_width), ' |',
commatize(isqrt(p), isqrt_width));
inc(n, 2);
p := p * 49;
until (n > 73);
CloseFile(f);
end.
Phix[edit]
See also Integer_roots#Phix for a simpler and shorter example using the mpz_root() routine, or better yet just use mpz_root() directly (that is, rather than the isqrt() below).
include mpfr.e
function isqrt(mpz x)
if mpz_cmp_si(x,0)<0 then
crash("Argument cannot be negative.")
end if
mpz q = mpz_init(1),
r = mpz_init(0),
t = mpz_init(),
z = mpz_init_set(x)
while mpz_cmp(q,x)<= 0 do
mpz_mul_si(q,q,4)
end while
while mpz_cmp_si(q,1)>0 do
assert(mpz_fdiv_q_ui(q, q, 4)=0)
mpz_sub(t,z,r)
mpz_sub(t,t,q)
assert(mpz_fdiv_q_ui(r, r, 2)=0)
if mpz_cmp_si(t,0) >= 0 then
mpz_set(z,t)
mpz_add(r,r,q)
end if
end while
-- return r
return shorten(mpz_get_str(r,10,true))
end function
printf(1,"The integer square roots of integers from 0 to 65 are:\n")
for i=0 to 65 do
printf(1,"%s ", {isqrt(mpz_init(i))})
end for
printf(1,"\n\npower 7 ^ power integer square root\n")
printf(1,"----- --------------------------------------------------------- ----------------------------------------------------------\n")
mpz pow7 = mpz_init(7)
for i=1 to 9000 do
if (i<=73 and remainder(i,2)=1)
or (i<100 and remainder(i,10)=5)
or (i<1000 and remainder(i,100)=0)
or remainder(i,1000)=0 then
printf(1,"%4d %58s %60s\n", {i, shorten(mpz_get_str(pow7,10,true)),isqrt(pow7)})
end if
mpz_mul_si(pow7,pow7,7)
end for
- Output:
The integer square roots of integers from 0 to 65 are: 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 power 7 ^ power integer square root ----- --------------------------------------------------------- ---------------------------------------------------------- 1 7 2 3 343 18 5 16,807 129 7 823,543 907 9 40,353,607 6,352 11 1,977,326,743 44,467 13 96,889,010,407 311,269 15 4,747,561,509,943 2,178,889 17 232,630,513,987,207 15,252,229 19 11,398,895,185,373,143 106,765,608 21 558,545,864,083,284,007 747,359,260 23 27,368,747,340,080,916,343 5,231,514,822 25 1,341,068,619,663,964,900,807 36,620,603,758 27 65,712,362,363,534,280,139,543 256,344,226,312 29 3,219,905,755,813,179,726,837,607 1,794,409,584,184 31 157,775,382,034,845,806,615,042,743 12,560,867,089,291 33 7,730,993,719,707,444,524,137,094,407 87,926,069,625,040 35 378,818,692,265,664,781,682,717,625,943 615,482,487,375,282 37 18,562,115,921,017,574,302,453,163,671,207 4,308,377,411,626,977 39 909,543,680,129,861,140,820,205,019,889,143 30,158,641,881,388,842 41 44,567,640,326,363,195,900,190,045,974,568,007 211,110,493,169,721,897 43 2,183,814,375,991,796,599,109,312,252,753,832,343 1,477,773,452,188,053,281 45 107,006,904,423,598,033,356,356,300,384,937,784,807 10,344,414,165,316,372,973 47 5,243,338,316,756,303,634,461,458,718,861,951,455,543 72,410,899,157,214,610,812 49 256,923,577,521,058,878,088,611,477,224,235,621,321,607 506,876,294,100,502,275,687 51 12,589,255,298,531,8...,987,545,444,758,743 (44 digits) 3,548,134,058,703,515,929,815 53 616,873,509,628,062,...,389,726,793,178,407 (45 digits) 24,836,938,410,924,611,508,707 55 30,226,801,971,775,0...,096,612,865,741,943 (47 digits) 173,858,568,876,472,280,560,953 57 1,481,113,296,616,97...,734,030,421,355,207 (49 digits) 1,217,009,982,135,305,963,926,677 59 72,574,551,534,231,9...,967,490,646,405,143 (50 digits) 8,519,069,874,947,141,747,486,745 61 3,556,153,025,177,36...,407,041,673,852,007 (52 digits) 59,633,489,124,629,992,232,407,216 63 174,251,498,233,690,...,945,042,018,748,343 (54 digits) 417,434,423,872,409,945,626,850,517 65 8,538,323,413,450,84...,307,058,918,668,807 (55 digits) 2,922,040,967,106,869,619,387,953,625 67 418,377,847,259,091,...,045,887,014,771,543 (57 digits) 20,454,286,769,748,087,335,715,675,381 69 20,500,514,515,695,4...,248,463,723,805,607 (59 digits) 143,180,007,388,236,611,350,009,727,669 71 1,004,525,211,269,07...,174,722,466,474,743 (61 digits) 1,002,260,051,717,656,279,450,068,093,686 73 49,221,735,352,184,8...,561,400,857,262,407 (62 digits) 7,015,820,362,023,593,956,150,476,655,802 75 2,411,865,032,257,05...,508,642,005,857,943 (64 digits) 49,110,742,534,165,157,693,053,336,590,618 85 681,292,175,541,205,...,256,581,907,552,807 (72 digits) 825,404,249,771,713,805,347,147,428,078,522,216 95 192,448,176,927,753,...,224,874,137,973,943 (81 digits) 13,872,569,225,913,193,926,469,506,823,715,722,892,042 100 3,234,476,509,624,75...,459,636,928,060,001 (85 digits) 1,798,465,042,647,41...,569,649,349,251,249 (43 digits) 200 10,461,838,291,314,3...,534,637,456,120,001 (170 digits) 3,234,476,509,624,75...,459,636,928,060,001 (85 digits) 300 33,838,570,200,749,1...,841,001,584,180,001 (254 digits) 5,817,092,933,824,34...,721,127,496,191,249 (127 digits) 400 109,450,060,433,611,...,994,729,312,240,001 (339 digits) 10,461,838,291,314,3...,534,637,456,120,001 (170 digits) 500 354,013,649,449,525,...,611,820,640,300,001 (423 digits) 18,815,250,448,759,0...,761,742,043,131,249 (212 digits) 600 1,145,048,833,231,02...,308,275,568,360,001 (508 digits) 33,838,570,200,749,1...,841,001,584,180,001 (254 digits) 700 3,703,633,553,458,98...,700,094,096,420,001 (592 digits) 60,857,485,599,217,6...,075,492,990,071,249 (296 digits) 800 11,979,315,728,921,1...,403,276,224,480,001 (677 digits) 109,450,060,433,611,...,994,729,312,240,001 (339 digits) 900 38,746,815,326,573,9...,033,821,952,540,001 (761 digits) 196,842,107,605,496,...,046,380,337,011,249 (381 digits) 1000 125,325,663,996,571,...,207,731,280,600,001 (846 digits) 354,013,649,449,525,...,611,820,640,300,001 (423 digits) 2000 15,706,522,056,181,6...,351,822,561,200,001 (1,691 digits) 125,325,663,996,571,...,207,731,280,600,001 (846 digits) 3000 1,968,430,305,767,76...,432,273,841,800,001 (2,536 digits) 44,366,995,681,111,4...,787,731,920,900,001 (1,268 digits) 4000 246,694,835,101,319,...,449,085,122,400,001 (3,381 digits) 15,706,522,056,181,6...,351,822,561,200,001 (1,691 digits) 5000 30,917,194,013,597,6...,402,256,403,000,001 (4,226 digits) 5,560,323,193,268,32...,900,003,201,500,001 (2,113 digits) 6000 3,874,717,868,664,96...,291,787,683,600,001 (5,071 digits) 1,968,430,305,767,76...,432,273,841,800,001 (2,536 digits) 7000 485,601,589,689,818,...,117,678,964,200,001 (5,916 digits) 696,851,196,231,891,...,948,634,482,100,001 (2,958 digits) 8000 60,858,341,665,667,3...,879,930,244,800,001 (6,761 digits) 246,694,835,101,319,...,449,085,122,400,001 (3,381 digits) 9000 7,627,112,078,979,99...,578,541,525,400,001 (7,606 digits) 87,333,338,874,567,2...,933,625,762,700,001 (3,803 digits)
(Note that pre-0.8.2 the "(NNN digits)" count includes commas)
Raku[edit]
Since there is already the task Integer roots that covers exactly this operation, with the caveat that it will calculate any nth root (including 2) not just square roots, we'll refer you to that.
See the Integer roots Raku entry.
REXX[edit]
A fair amount of code was included so that the output aligns correctly.
/*REXX program computes and displays the Isqrt (integer square root) of some integers.*/
numeric digits 200 /*insure 'nuff decimal digs for results*/
parse arg range power base . /*obtain optional arguments from the CL*/
if range=='' | range=="," then range= 0..65 /*Not specified? Then use the default.*/
if power=='' | power=="," then power= 1..73 /* " " " " " " */
if base =='' | base =="," then base = 7 /* " " " " " " */
parse var range rLO '..' rHI; if rHI=='' then rHI= rLO /*handle a range? */
parse var power pLO '..' pHI; if pHI=='' then pHI= pLO /* " " " */
$=
do j=rLO to rHI while rHI>0 /*compute Isqrt for a range of integers*/
$= $ commas( Isqrt(j) ) /*append the Isqrt to a list for output*/
end /*j*/
$= strip($) /*elide the leading blank in the list. */
say center(' Isqrt for numbers: ' rLO " ──► " rHI' ', length($), "─")
say strip($) /*$ has a leading blank for 1st number*/
say
z= base ** pHI /*compute max. exponentiation product.*/
Lp= max(30, length( commas( z) ) ) /*length of " " " */
Lr= max(20, length( commas( Isqrt(z) ) ) ) /* " " " " " Isqrt of above.*/
say 'index' center(base"**index", Lp) center('Isqrt', Lr) /*show a title.*/
say '─────' copies("─", Lp) copies('─', Lr) /* " " header*/
do j=pLO to pHI by 2 while pHI>0; x= base ** j
say center(j, 5) right( commas(x), Lp) right( commas( Isqrt(x) ), Lr)
end /*j*/ /* [↑] show a bunch of powers & Isqrt.*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _
/*──────────────────────────────────────────────────────────────────────────────────────*/
Isqrt: procedure; parse arg x /*obtain the only passed argument X. */
x= x % 1 /*convert possible real X to an integer*/ /* ◄■■■■■■■ optional. */
q= 1 /*initialize the Q variable to unity.*/
do until q>x /*find a Q that is greater than X. */
q= q * 4 /*multiply Q by four. */
end /*until*/
r= 0 /*R: will be the integer sqrt of X. */
do while q>1 /*keep processing while Q is > than 1*/
q= q % 4 /*divide Q by four (no remainder). */
t= x - r - q /*compute a temporary variable. */
r= r % 2 /*divide R by two (no remainder). */
if t >= 0 then do /*if T is non─negative ... */
x= t /*recompute the value of X */
r= r + q /* " " " " R */
end
end /*while*/
return r /*return the integer square root of X. */
- output when using the default inputs:
───────────────────────────────────────────────── Isqrt for numbers: 0 ──► 65 ────────────────────────────────────────────────── 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 index 7**index Isqrt ───── ────────────────────────────────────────────────────────────────────────────────── ───────────────────────────────────────── 1 7 2 3 343 18 5 16,807 129 7 823,543 907 9 40,353,607 6,352 11 1,977,326,743 44,467 13 96,889,010,407 311,269 15 4,747,561,509,943 2,178,889 17 232,630,513,987,207 15,252,229 19 11,398,895,185,373,143 106,765,608 21 558,545,864,083,284,007 747,359,260 23 27,368,747,340,080,916,343 5,231,514,822 25 1,341,068,619,663,964,900,807 36,620,603,758 27 65,712,362,363,534,280,139,543 256,344,226,312 29 3,219,905,755,813,179,726,837,607 1,794,409,584,184 31 157,775,382,034,845,806,615,042,743 12,560,867,089,291 33 7,730,993,719,707,444,524,137,094,407 87,926,069,625,040 35 378,818,692,265,664,781,682,717,625,943 615,482,487,375,282 37 18,562,115,921,017,574,302,453,163,671,207 4,308,377,411,626,977 39 909,543,680,129,861,140,820,205,019,889,143 30,158,641,881,388,842 41 44,567,640,326,363,195,900,190,045,974,568,007 211,110,493,169,721,897 43 2,183,814,375,991,796,599,109,312,252,753,832,343 1,477,773,452,188,053,281 45 107,006,904,423,598,033,356,356,300,384,937,784,807 10,344,414,165,316,372,973 47 5,243,338,316,756,303,634,461,458,718,861,951,455,543 72,410,899,157,214,610,812 49 256,923,577,521,058,878,088,611,477,224,235,621,321,607 506,876,294,100,502,275,687 51 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 3,548,134,058,703,515,929,815 53 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 24,836,938,410,924,611,508,707 55 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 173,858,568,876,472,280,560,953 57 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 1,217,009,982,135,305,963,926,677 59 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 8,519,069,874,947,141,747,486,745 61 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 59,633,489,124,629,992,232,407,216 63 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 417,434,423,872,409,945,626,850,517 65 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 2,922,040,967,106,869,619,387,953,625 67 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 20,454,286,769,748,087,335,715,675,381 69 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 143,180,007,388,236,611,350,009,727,669 71 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686 73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802
Ruby[edit]
class Integer
def commatize
self.to_s.gsub( /(\d)(?=\d{3}+(?:\.|$))(\d{3}\..*)?/, "\\1,\\2")
end
end
puts (0..65).map{|n| Integer.sqrt(n) }.join(" ")
1.step(73, 2) do |n|
print "#{n}:\t"
puts Integer.sqrt(7**n).commatize
end
- Output:
0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 1: 2 3: 18 5: 129 7: 907 9: 6,352 11: 44,467 13: 311,269 15: 2,178,889 17: 15,252,229 19: 106,765,608 21: 747,359,260 23: 5,231,514,822 25: 36,620,603,758 27: 256,344,226,312 29: 1,794,409,584,184 31: 12,560,867,089,291 33: 87,926,069,625,040 35: 615,482,487,375,282 37: 4,308,377,411,626,977 39: 30,158,641,881,388,842 41: 211,110,493,169,721,897 43: 1,477,773,452,188,053,281 45: 10,344,414,165,316,372,973 47: 72,410,899,157,214,610,812 49: 506,876,294,100,502,275,687 51: 3,548,134,058,703,515,929,815 53: 24,836,938,410,924,611,508,707 55: 173,858,568,876,472,280,560,953 57: 1,217,009,982,135,305,963,926,677 59: 8,519,069,874,947,141,747,486,745 61: 59,633,489,124,629,992,232,407,216 63: 417,434,423,872,409,945,626,850,517 65: 2,922,040,967,106,869,619,387,953,625 67: 20,454,286,769,748,087,335,715,675,381 69: 143,180,007,388,236,611,350,009,727,669 71: 1,002,260,051,717,656,279,450,068,093,686 73: 7,015,820,362,023,593,956,150,476,655,802
Swift[edit]
Requires the attaswift BigInt package.
import BigInt
func integerSquareRoot<T: BinaryInteger>(_ num: T) -> T {
var x: T = num
var q: T = 1
while q <= x {
q <<= 2
}
var r: T = 0
while q > 1 {
q >>= 2
let t: T = x - r - q
r >>= 1
if t >= 0 {
x = t
r += q
}
}
return r
}
func pad(string: String, width: Int) -> String {
if string.count >= width {
return string
}
return String(repeating: " ", count: width - string.count) + string
}
func commatize<T: BinaryInteger>(_ num: T) -> String {
let string = String(num)
var result = String()
result.reserveCapacity(4 * string.count / 3)
var i = 0
for ch in string {
if i > 0 && i % 3 == string.count % 3 {
result += ","
}
result.append(ch)
i += 1
}
return result
}
print("Integer square root for numbers 0 to 65:")
for n in 0...65 {
print(integerSquareRoot(n), terminator: " ")
}
let powerWidth = 83
let isqrtWidth = 42
print("\n\nInteger square roots of odd powers of 7 from 1 to 73:")
print(" n |\(pad(string: "7 ^ n", width: powerWidth)) |\(pad(string: "isqrt(7 ^ n)", width: isqrtWidth))")
print(String(repeating: "-", count: powerWidth + isqrtWidth + 6))
var p: BigInt = 7
for n in stride(from: 1, through: 73, by: 2) {
let power = pad(string: commatize(p), width: powerWidth)
let isqrt = pad(string: commatize(integerSquareRoot(p)), width: isqrtWidth)
print("\(pad(string: String(n), width: 2)) |\(power) |\(isqrt)")
p *= 49
}
- Output:
Integer square root for numbers 0 to 65: 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 Integer square roots of odd powers of 7 from 1 to 73: n | 7 ^ n | isqrt(7 ^ n) ----------------------------------------------------------------------------------------------------------------------------------- 1 | 7 | 2 3 | 343 | 18 5 | 16,807 | 129 7 | 823,543 | 907 9 | 40,353,607 | 6,352 11 | 1,977,326,743 | 44,467 13 | 96,889,010,407 | 311,269 15 | 4,747,561,509,943 | 2,178,889 17 | 232,630,513,987,207 | 15,252,229 19 | 11,398,895,185,373,143 | 106,765,608 21 | 558,545,864,083,284,007 | 747,359,260 23 | 27,368,747,340,080,916,343 | 5,231,514,822 25 | 1,341,068,619,663,964,900,807 | 36,620,603,758 27 | 65,712,362,363,534,280,139,543 | 256,344,226,312 29 | 3,219,905,755,813,179,726,837,607 | 1,794,409,584,184 31 | 157,775,382,034,845,806,615,042,743 | 12,560,867,089,291 33 | 7,730,993,719,707,444,524,137,094,407 | 87,926,069,625,040 35 | 378,818,692,265,664,781,682,717,625,943 | 615,482,487,375,282 37 | 18,562,115,921,017,574,302,453,163,671,207 | 4,308,377,411,626,977 39 | 909,543,680,129,861,140,820,205,019,889,143 | 30,158,641,881,388,842 41 | 44,567,640,326,363,195,900,190,045,974,568,007 | 211,110,493,169,721,897 43 | 2,183,814,375,991,796,599,109,312,252,753,832,343 | 1,477,773,452,188,053,281 45 | 107,006,904,423,598,033,356,356,300,384,937,784,807 | 10,344,414,165,316,372,973 47 | 5,243,338,316,756,303,634,461,458,718,861,951,455,543 | 72,410,899,157,214,610,812 49 | 256,923,577,521,058,878,088,611,477,224,235,621,321,607 | 506,876,294,100,502,275,687 51 | 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 | 3,548,134,058,703,515,929,815 53 | 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 | 24,836,938,410,924,611,508,707 55 | 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 | 173,858,568,876,472,280,560,953 57 | 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 | 1,217,009,982,135,305,963,926,677 59 | 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 | 8,519,069,874,947,141,747,486,745 61 | 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 | 59,633,489,124,629,992,232,407,216 63 | 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 | 417,434,423,872,409,945,626,850,517 65 | 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 | 2,922,040,967,106,869,619,387,953,625 67 | 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 | 20,454,286,769,748,087,335,715,675,381 69 | 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 | 143,180,007,388,236,611,350,009,727,669 71 | 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 | 1,002,260,051,717,656,279,450,068,093,686 73 | 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 | 7,015,820,362,023,593,956,150,476,655,802
Tiny BASIC[edit]
Tiny BASIC does not support string formatting or concatenation, and is limited to integer arithmetic on numbers no greater than 32,767. The isqrt of 0-65 and the first two odd powers of 7 are shown in column format. The algorithm itself (the interesting part) begins on line 100.
10 LET X = 0
20 GOSUB 100
30 PRINT R
40 LET X = X + 1
50 IF X < 66 THEN GOTO 20
70 PRINT "---"
71 LET X = 7
72 GOSUB 100
73 PRINT R
77 LET X = 343
78 GOSUB 100
79 PRINT R
90 END
100 REM integer square root function
110 LET Q = 1
120 IF Q > X THEN GOTO 150
130 LET Q = Q * 4
140 GOTO 120
150 LET Z = X
160 LET R = 0
170 IF Q <= 1 THEN RETURN
180 LET Q = Q / 4
190 LET T = Z - R - Q
200 LET R = R / 2
210 IF T < 0 THEN GOTO 170
220 LET Z = T
230 LET R = R + Q
240 GOTO 170
Visual Basic .NET[edit]
Imports System
Imports System.Console
Imports BI = System.Numerics.BigInteger
Module Module1
Function isqrt(ByVal x As BI) As BI
Dim t As BI, q As BI = 1, r As BI = 0
While q <= x : q <<= 2 : End While
While q > 1 : q >>= 2 : t = x - r - q : r >>= 1
If t >= 0 Then x = t : r += q
End While : Return r
End Function
Sub Main()
Const max As Integer = 73, smax As Integer = 65
Dim power_width As Integer = ((BI.Pow(7, max).ToString().Length \ 3) << 2) + 3,
isqrt_width As Integer = (power_width + 1) >> 1,
n as Integer
WriteLine("Integer square root for numbers 0 to {0}:", smax)
For n = 0 To smax : Write("{0} ", (n \ 10).ToString().Replace("0", " "))
Next : WriteLine()
For n = 0 To smax : Write("{0} ", n Mod 10) : Next : WriteLine()
WriteLine(New String("-"c, (smax << 1) + 1))
For n = 0 To smax : Write("{0} ", isqrt(n)) : Next
WriteLine(vbLf & vbLf & "Integer square roots of odd powers of 7 from 1 to {0}:", max)
Dim s As String = String.Format("[0,2] |[1,{0}:n0] |[2,{1}:n0]",
power_width, isqrt_width).Replace("[", "{").Replace("]", "}")
WriteLine(s, "n", "7 ^ n", "isqrt(7 ^ n)")
WriteLine(New String("-"c, power_width + isqrt_width + 6))
Dim p As BI = 7 : n = 1 : While n <= max
WriteLine(s, n, p, isqrt(p)) : n += 2 : p = p * 49
End While
End Sub
End Module
- Output:
Integer square root for numbers 0 to 65:
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
-----------------------------------------------------------------------------------------------------------------------------------
0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8
Integer square roots of odd powers of 7 from 1 to 73:
n | 7 ^ n | isqrt(7 ^ n)
-----------------------------------------------------------------------------------------------------------------------------------
1 | 7 | 2
3 | 343 | 18
5 | 16,807 | 129
7 | 823,543 | 907
9 | 40,353,607 | 6,352
11 | 1,977,326,743 | 44,467
13 | 96,889,010,407 | 311,269
15 | 4,747,561,509,943 | 2,178,889
17 | 232,630,513,987,207 | 15,252,229
19 | 11,398,895,185,373,143 | 106,765,608
21 | 558,545,864,083,284,007 | 747,359,260
23 | 27,368,747,340,080,916,343 | 5,231,514,822
25 | 1,341,068,619,663,964,900,807 | 36,620,603,758
27 | 65,712,362,363,534,280,139,543 | 256,344,226,312
29 | 3,219,905,755,813,179,726,837,607 | 1,794,409,584,184
31 | 157,775,382,034,845,806,615,042,743 | 12,560,867,089,291
33 | 7,730,993,719,707,444,524,137,094,407 | 87,926,069,625,040
35 | 378,818,692,265,664,781,682,717,625,943 | 615,482,487,375,282
37 | 18,562,115,921,017,574,302,453,163,671,207 | 4,308,377,411,626,977
39 | 909,543,680,129,861,140,820,205,019,889,143 | 30,158,641,881,388,842
41 | 44,567,640,326,363,195,900,190,045,974,568,007 | 211,110,493,169,721,897
43 | 2,183,814,375,991,796,599,109,312,252,753,832,343 | 1,477,773,452,188,053,281
45 | 107,006,904,423,598,033,356,356,300,384,937,784,807 | 10,344,414,165,316,372,973
47 | 5,243,338,316,756,303,634,461,458,718,861,951,455,543 | 72,410,899,157,214,610,812
49 | 256,923,577,521,058,878,088,611,477,224,235,621,321,607 | 506,876,294,100,502,275,687
51 | 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 | 3,548,134,058,703,515,929,815
53 | 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 | 24,836,938,410,924,611,508,707
55 | 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 | 173,858,568,876,472,280,560,953
57 | 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 | 1,217,009,982,135,305,963,926,677
59 | 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 | 8,519,069,874,947,141,747,486,745
61 | 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 | 59,633,489,124,629,992,232,407,216
63 | 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 | 417,434,423,872,409,945,626,850,517
65 | 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 | 2,922,040,967,106,869,619,387,953,625
67 | 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 | 20,454,286,769,748,087,335,715,675,381
69 | 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 | 143,180,007,388,236,611,350,009,727,669
71 | 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 | 1,002,260,051,717,656,279,450,068,093,686
73 | 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 | 7,015,820,362,023,593,956,150,476,655,802
Wren[edit]
import "/big" for BigInt
import "/fmt" for Fmt
var isqrt = Fn.new { |x|
if (!(x is BigInt && x >= BigInt.zero)) {
Fiber.abort("Argument must be a non-negative big integer.")
}
var q = BigInt.one
while (q <= x) q = q * 4
var z = x
var r = BigInt.zero
while (q > BigInt.one) {
q = q >> 2
var t = z - r - q
r = r >> 1
if (t >= 0) {
z = t
r = r + q
}
}
return r
}
System.print("The integer square roots of integers from 0 to 65 are:")
for (i in 0..65) System.write("%(isqrt.call(BigInt.new(i))) ")
System.print()
System.print("\nThe integer square roots of powers of 7 from 7^1 up to 7^73 are:\n")
System.print("power 7 ^ power integer square root")
System.print("----- --------------------------------------------------------------------------------- -----------------------------------------")
var pow7 = BigInt.new(7)
var bi49 = BigInt.new(49)
var i = 1
while (i <= 73) {
Fmt.print("$2d $,84s $,41s", i, pow7, isqrt.call(pow7))
pow7 = pow7 * bi49
i = i + 2
}
- Output:
The integer square roots of integers from 0 to 65 are: 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 The integer square roots of odd powers of 7 from 7^1 up to 7^73 are: power 7 ^ power integer square root ----- --------------------------------------------------------------------------------- ----------------------------------------- 1 7 2 3 343 18 5 16,807 129 7 823,543 907 9 40,353,607 6,352 11 1,977,326,743 44,467 13 96,889,010,407 311,269 15 4,747,561,509,943 2,178,889 17 232,630,513,987,207 15,252,229 19 11,398,895,185,373,143 106,765,608 21 558,545,864,083,284,007 747,359,260 23 27,368,747,340,080,916,343 5,231,514,822 25 1,341,068,619,663,964,900,807 36,620,603,758 27 65,712,362,363,534,280,139,543 256,344,226,312 29 3,219,905,755,813,179,726,837,607 1,794,409,584,184 31 157,775,382,034,845,806,615,042,743 12,560,867,089,291 33 7,730,993,719,707,444,524,137,094,407 87,926,069,625,040 35 378,818,692,265,664,781,682,717,625,943 615,482,487,375,282 37 18,562,115,921,017,574,302,453,163,671,207 4,308,377,411,626,977 39 909,543,680,129,861,140,820,205,019,889,143 30,158,641,881,388,842 41 44,567,640,326,363,195,900,190,045,974,568,007 211,110,493,169,721,897 43 2,183,814,375,991,796,599,109,312,252,753,832,343 1,477,773,452,188,053,281 45 107,006,904,423,598,033,356,356,300,384,937,784,807 10,344,414,165,316,372,973 47 5,243,338,316,756,303,634,461,458,718,861,951,455,543 72,410,899,157,214,610,812 49 256,923,577,521,058,878,088,611,477,224,235,621,321,607 506,876,294,100,502,275,687 51 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 3,548,134,058,703,515,929,815 53 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 24,836,938,410,924,611,508,707 55 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 173,858,568,876,472,280,560,953 57 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 1,217,009,982,135,305,963,926,677 59 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 8,519,069,874,947,141,747,486,745 61 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 59,633,489,124,629,992,232,407,216 63 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 417,434,423,872,409,945,626,850,517 65 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 2,922,040,967,106,869,619,387,953,625 67 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 20,454,286,769,748,087,335,715,675,381 69 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 143,180,007,388,236,611,350,009,727,669 71 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686 73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802
