Pell's equation: Difference between revisions

'''Pell's equation''' &nbsp; (also called the '''Pell–Fermat''' equation) &nbsp; is a &nbsp; [https://en.wikipedia.org/wiki/Diophantine_equation <u>Diophantine equation</u>] &nbsp; of the form:

 

 

with integer solutions for &nbsp; '''x''' &nbsp; and &nbsp; '''y''', &nbsp; where &nbsp; '''n''' &nbsp; is a given non-square positive integer.

:* &nbsp; Wikipedia entry: [https://en.wikipedia.org/wiki/Pell%27s_equation <u>Pell's equation</u>].

<br><br>

 

=={{header|ALGOL 68}}==

{{Trans|Sidef}} Also tests for a trival solution only (if n is a perfect square only 1, 0 is solution).

{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}

# find solutions to Pell's eqauation: x^2 - ny^2 = 1 for integer x, y, n #

MODE BIGINT = LONG LONG INT;

print( ("x^2 - ", whole( n, -3 ), " * y^2 = 1 for x = ", whole( v1 OF r, -21), " and y = ", whole( v2 OF r, -21 ), newline ) )

OD

{{out}}

<pre>

x^2 - 277 * y^2 = 1 for x = 159150073798980475849 and y = 9562401173878027020

</pre>

 

=={{header|C}}==

{{trans|ALGOL 68}}

For n = 277, the x value is not correct because 64-bits is not enough to represent the value.

#include <stdbool.h>

#include <stdint.h>

void test(int n) {

struct Pair r = solvePell(n);

}

 

 

return 0;

{{out}}

 

=={{header|C++}}==

{{trans|C}}

As with the C solution, the output for n = 277 is not correct because 64-bits is not enough to represent the value.

#include <iostream>

#include <tuple>

 

return 0;

{{out}}

<pre>x^2 - 61 * y^2 = 1 for x = 1766319049 and y = 226153980

=={{header|C sharp|C#}}==

{{trans|Sidef}}

using System.Numerics;

 

}

}

{{out}}

<pre>x^2 - 61 * y^2 = 1 for x = 1,766,319,049 and y = 226,153,980

=={{header|D}}==

{{trans|C#}}

import std.math;

import std.stdio;

writefln("x^2 - %3d * y^2 = 1 for x = %27d and y = %25d", n, x, y);

}

{{out}}

<pre>x^2 - 61 * y^2 = 1 for x = 1766319049 and y = 226153980

x^2 - 181 * y^2 = 1 for x = 2469645423824185801 and y = 183567298683461940

x^2 - 277 * y^2 = 1 for x = 159150073798980475849 and y = 9562401173878027020</pre>

 

=={{header|Factor}}==

{{trans|Sidef}}

 

:: solve-pell ( n -- a b )

dup solve-pell

"x^2 - %3d*y^2 = 1 for x = %-21d and y = %d\n" printf

{{out}}

<pre>

{{trans|Visual Basic .NET}}

'''for n = 277 the result is wrong, I do not know if you can represent such large numbers in FreeBasic!'''

Sub Fun(Byref a As LongInt, Byref b As LongInt, c As Integer)

Dim As LongInt t

Print Using "x^2 - ### * y^2 = 1 for x = ##################### and y = #####################"; n(i); x; y

Next i

{{out}}

<pre>

=={{header|Go}}==

{{trans|Sidef}}

 

import (

fmt.Printf("x^2 - %3d*y^2 = 1 for x = %-21s and y = %s\n", n, x, y)

}

 

{{out}}

x^2 - 181*y^2 = 1 for x = 2469645423824185801 and y = 183567298683461940

x^2 - 277*y^2 = 1 for x = 159150073798980475849 and y = 9562401173878027020

</pre>

 

=={{header|Java}}==

import java.math.BigInteger;

import java.text.NumberFormat;

 

}

 

{{out}}

x = 2,565,007,112,872,132,129,669,406,439,503,954,211,359,492,684,749,762,901,360,167,370,740,763,715,001,557,789,090,674,216,330,243,703,833,040,774,221,628,256,858,633,287,876,949,448,689,668,281,446,637,464,359,482,677,366,420,261,407,112,316,649,010,675,881,349,744,201

y = 27,126,610,172,119,035,540,864,542,981,075,550,089,190,381,938,849,116,323,732,855,930,990,771,728,447,597,698,969,628,164,719,475,714,805,646,913,222,890,277,024,408,337,458,564,351,161,990,641,948,210,581,361,708,373,955,113,191,451,102,494,265,278,824,127,994,180

</pre>

 

=={{header|Julia}}==

{{trans|C#}}

x = BigInt(floor(sqrt(n)))

y, z, r = x, BigInt(1), x << 1

println("x\u00b2 - $target", "y\u00b2 = 1 for x = $x and y = $y")

end

<pre>

x² - 61y² = 1 for x = 1766319049 and y = 226153980

=={{header|Kotlin}}==

{{trans|C#}}

import kotlin.math.sqrt

 

println("x^2 - %3d * y^2 = 1 for x = %,27d and y = %,25d".format(it, x.value, y.value))

}

{{out}}

<pre>x^2 - 61 * y^2 = 1 for x = 1,766,319,049 and y = 226,153,980

x^2 - 181 * y^2 = 1 for x = 2,469,645,423,824,185,801 and y = 183,567,298,683,461,940

x^2 - 277 * y^2 = 1 for x = 159,150,073,798,980,475,849 and y = 9,562,401,173,878,027,020</pre>

 

=={{header|langur}}==

{{trans|D}}

 

var .e1, .e2, .f1, .f2 = 1, 0, 0, 1

 

for {

.r = (.x + .y) \ .z

.e1, .e2 = .fun(.e1, .e2, .r)

.f1, .f2 = .fun(.f1, .f2, .r)

val .b, .a = .fun(.e2, .f2, .x)

}

}

 

# format number string with commas

if .s[1] == '-' {

.neg, .s = "-", rest .s

for .n in [61, 109, 181, 277, 8941] {

val .x, .y = .solvePell(.n)

}

 

{{out}}

x = 2,565,007,112,872,132,129,669,406,439,503,954,211,359,492,684,749,762,901,360,167,370,740,763,715,001,557,789,090,674,216,330,243,703,833,040,774,221,628,256,858,633,287,876,949,448,689,668,281,446,637,464,359,482,677,366,420,261,407,112,316,649,010,675,881,349,744,201

y = 27,126,610,172,119,035,540,864,542,981,075,550,089,190,381,938,849,116,323,732,855,930,990,771,728,447,597,698,969,628,164,719,475,714,805,646,913,222,890,277,024,408,337,458,564,351,161,990,641,948,210,581,361,708,373,955,113,191,451,102,494,265,278,824,127,994,180

</pre>

 

=={{header|Perl}}==

my ($n) = @_;

 

my ($x, $y) = solve_pell($n);

printf("x^2 - %3d*y^2 = 1 for x = %-21s and y = %s\n", $n, $x, $y);

{{out}}

<pre>

{{trans|C#}}

{{trans|Go}}

This now ignores the nonsquare part of the task spec, returning {1,0}.

{{out}}

<pre>

</pre>

 

=={{header|Python}}==

{{trans|D}}

 

x = int(math.sqrt(n))

while True:

y = r * z - y

r = (x + y) // z

 

for n in [61, 109, 181, 277]:

{{out}}

<pre>x^2 - 61 * y^2 = 1 for x = 1766319049 and y = 226153980

{{trans|Perl}}

 

 

sub pell (Int $n) {

my ($x, $y) = pell($n);

printf "x² - %sy² = 1 for:\n\tx = %s\n\ty = %s\n\n", $n, |($x, $y)».&comma;

{{out}}

<pre>x² - 61y² = 1 for:

 

=={{header|REXX}}==

numeric digits 2200 /*ensure enough decimal digs for answer*/

parse arg $ /*obtain optional arguments from the CL*/

if $=='' | $=="," then $= 61 109 181 277 /*Not specified? Then use the defaults*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

floor: procedure; parse arg x; _= x % 1; return _ - (x < 0) * (x \= _)

/*──────────────────────────────────────────────────────────────────────────────────────*/

z= 1; r= x + x

do until ( (e2 + x*f2)**2 - n*f2*f2) == 1

end /*until*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

</pre>

 

=={{header|Ruby}}==

{{trans|Sidef}}

x = Integer.sqrt(n)

y = x

 

[61, 109, 181, 277].each {|n| puts "x*x - %3s*y*y = 1 for x = %-21s and y = %s" % [n, *solve_pell(n)]}

{{Out}}

<pre>

 

</pre>

 

=={{header|Sidef}}==

 

var x = n.isqrt

var (x, y) = solve_pell(n)

printf("x^2 - %3d*y^2 = 1 for x = %-21s and y = %s\n", n, x, y)

{{out}}

<pre>

{{libheader|AttaSwift's BigInt}}

 

func swap(_ a: inout T, _ b: inout T, mul by: T) {

(a, b) = (b, b * by + a)

 

print("x\u{00b2} - \(n)y\u{00b2} = 1 for x = \(x) and y = \(y)")

 

{{out}}

=={{header|Visual Basic .NET}}==

{{trans|Sidef}}

 

Module Module1

Next

End Sub

{{out}}

<pre>x^2 - 61 * y^2 = 1 for x = 1,766,319,049 and y = 226,153,980

x^2 - 181 * y^2 = 1 for x = 2,469,645,423,824,185,801 and y = 183,567,298,683,461,940

x^2 - 277 * y^2 = 1 for x = 159,150,073,798,980,475,849 and y = 9,562,401,173,878,027,020</pre>

 

=={{header|zkl}}==

{{libheader|GMP}} GNU Multiple Precision Arithmetic Library

{{trans|Raku}}

 

fcn solve_pell(n){

if (A*A - B*B*n == 1) return(A,B);

}

x,y:=solve_pell(n);

println("x^2 - %3d*y^2 = 1 for x = %-21d and y = %d".fmt(n,x,y));

 

{{out}}