Codegolf - Фундаментальное Решение Уравнения Пелла

Учитывая некоторое положительное целое число \$n\$, не являющееся квадратом, найдите фундаментальное решение \$(x,y)\$ соответствующего уравнения Пелля.

$$x^2 - n\cdot y^2 = 1$$

Подробности

• Фундаментальный \$(x,y)\$ — это пара целых чисел \$x,y\$, удовлетворяющая уравнению, где \$x\$ минимально и положительно. (Всегда существует тривиальное решение \$(x,y)=(1,0)\$, которое не учитывается.)
• Вы можете предположить, что \$n\$ не является квадратом.

Примеры

  n           x    y

1           -    -

2           3    2

3           2    1

4           -    -

5           9    4

6           5    2

7           8    3

8           3    1

9           -    -
10          19    6
11          10    3
12           7    2
13         649    180
14          15    4
15           4    1
16           -    -
17          33    8
18          17    4
19         170    39
20           9    2
21          55    12
22         197    42
23          24    5
24           5    1
25           -    -
26          51    10
27          26    5
28         127    24
29        9801    1820
30          11    2
31        1520    273
32          17    3
33          23    4
34          35    6
35           6    1
36           -    -
37          73    12
38          37    6
39          25    4
40          19    3
41        2049    320
42          13    2
43        3482    531
44         199    30
45         161    24
46       24335    3588
47          48    7
48           7    1
49           -    -
50          99    14
51          50    7
52         649    90
53       66249    9100
54         485    66
55          89    12
56          15    2
57         151    20
58       19603    2574
59         530    69
60          31    4
61  1766319049    226153980
62          63    8
63           8    1
64           -    -
65         129    16
66          65    8
67       48842    5967
68          33    4
69        7775    936
70         251    30
71        3480    413
72          17    2
73     2281249    267000
74        3699    430
75          26    3
76       57799    6630
77         351    40
78          53    6
79          80    9
80           9    1
81           -    -
82         163    18
83          82    9
84          55    6
85      285769    30996
86       10405    1122
87          28    3
88         197    21
89      500001    53000
90          19    2
91        1574    165
92        1151    120
93       12151    1260
94     2143295    221064
95          39    4
96          49    5
97    62809633    6377352
98          99    10
99          10    1
 

Соответствующие последовательности OEIS: А002350 А002349 А033313 А033317

#код-гольф #математика #теория чисел #абстрактная алгебра #полиномы

Пит, 612 кодов

Берет н со стандартного ввода. Выходы й затем х, разделенные пробелами.

Размер кода 1:

Размер кода 4, для удобства просмотра:

Объяснение

Проверить этот след NPiet, где показана программа, вычисляющая решение для входного значения 99.

Я не уверен, слышал ли я когда-либо об уравнении Пелла до этого задания, поэтому все следующее я взял из Википедии; в частности, эти разделы трех статей:

• Уравнение Пелла § Фундаментальное решение через цепные дроби
• Методы вычисления квадратных корней § Разложение цепной дроби
• Непрерывная дробь § Бесконечные цепные дроби и подходящие дроби

По сути, мы делаем следующее:

1. Получите \$n\$ из стандартного ввода.
2. Найдите \$\lfloor\sqrt n\rfloor\$, увеличивая счетчик до тех пор, пока его площадь не превысит \$n\$, а затем уменьшите его один раз. (Это первый цикл, который вы видите в трассировке, вверху слева.)
3. Настройте несколько переменных для вычисления \$x\$ и \$y\$ из цепной дроби \$\sqrt n\$.
4. Проверьте, соответствуют ли \$x\$ и \$y\$ уравнению Пелла. Если да, выведите значения (это ветвь вниз примерно на 2/3 пути), а затем выйдите (врезавшись в красный блок в крайнем левом углу).
5. Если нет, итеративно обновите переменные и вернитесь к шагу 4. (Это широкий цикл вправо, обратно через низ и воссоединение не совсем на полпути.)

Честно говоря, я понятия не имею, будет ли метод грубой силы короче, и я не собираюсь его пробовать! Хорошо, я попробовал.

Пит, 184 кода

Это альтернатива грубой силы, о которой я говорил (в мой другой ответ), что я не хотел писать. Вычисление решения занимает более 2 минут. н = 13. Мне очень не хочется это примерять н = 29... но это проверяется для каждого н до 20, поэтому я уверен, что это правильно.

Как и тот другой ответ, это требует н из стандартного ввода и вывода й затем х, разделенные пробелами.

Размер кода 1:

Размер кода 4, для удобства просмотра:

Объяснение

Вот NPiet трассировка для входного значения 5.

Это самый жестокий из методов грубой силы, перебирающий как \$x\$, так и \$y\$. Другие решения могут перебирать \$x\$ и затем вычислять \$y=\sqrt{\frac{x^2-1}{n}}\$, но они слабаки.

Начиная с \$x=2\$ и \$y=1\$, проверяется, решили ли \$x\$ и \$y\$ уравнение. Если да (вилка внизу справа), он выводит значения и завершает работу.

В противном случае он продолжается влево, где \$y\$ увеличивается и сравнивается с \$x\$. (Затем нужно немного изменить направление, чтобы следовать по зигзагообразному пути.)

В этом последнем сравнении путь разделяется вокруг середины левого угла. Если они равны, \$x\$ увеличивается, а \$y\$ возвращается к 1. И мы возвращаемся к проверке, является ли это решением.

У меня все еще есть свободное пространство, так что, возможно, я посмотрю, смогу ли я включить это вычисление квадратного корня без увеличения программы.

Брахилог, 16 байт

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 (x, y) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Попробуйте онлайн!

Объяснение

Париж/GP, 34 байта

В PARI/GP для этого почти есть встроенная функция: lambda i:[(x,y)for x in range(i**i)for y in range(x)if~-x**2==i*y**2][1] gives the fundamental unit of the квадратичное поле \$\mathbb{Q}(\sqrt{D})\$, где \$D\$ — дискриминант поля. Другими словами, lambda i:next((x,y)for x in range(2,i**i)for y in range(x)if~-x**2==i*y**2) solves the Pell's equation \$x^2 - n \cdot y^2 = \pm 1\$. So I have to take the square when its norm is \$-1\$.

Я не знаю, какой алгоритм он использует, но он работает даже тогда, когда \$n\$ не свободен от квадратов.

Ответы даются в виде n=>{for(int x=2,y;;x++)for(y=0;y<=x;y++)if(x*x-y*y*n==1)return(x,y);} , where y обозначает \$\sqrt{n}\$.

Попробуйте онлайн!

Язык Wolfram (Математика), 46 байт

Попробуйте онлайн!

05AB1E, 17 16 14 байт

Сэкономил байт благодаря Кевин Круйссен.
Выходы x

Попробуйте онлайн!

Объяснение

Java 8, 74 73 72 байта

-1 байт благодаря @Арно.
-1 байт благодаря @ОливьеГрегойр.

Попробуйте онлайн.

Объяснение:

R, 66 56 54 53 52 47 45 байт

полная программа

-1 -2 благодаря @Giuseppe

-7 благодаря @Giuseppe и @Robin Ryder

, 40 байт

Попробуйте онлайн!

Альтернативный ответ Jelly, менее запутанный, но более эффективный алгоритмически, когда x и y велики. Это находит подходящие дроби правильной цепной дроби, которые приближают квадратный корень из n, а затем проверяет, что решает уравнение Пелла. Теперь правильно находит период правильной цепной дроби.

Благодаря @TimPederick я также реализовал решение на основе целых чисел, которое должно обрабатывать любое число:Желе

, 68 байт

Попробуйте онлайн! Например, решение для 1234567890

JavaScript (ES7), 47 байт

Попробуйте онлайн! Ниже представлен альтернативный вариант 49 байт

версия, которая отслеживает \$x²-1\$ напрямую, а не возводит \$x\$ в квадрат на каждой итерации:

Попробуйте онлайн! Или мы можем пойти нерекурсивным путем для:

50 байт

TI-BASIC, 44 42 41 байт
Ввод: \$n\$.

Выходные данные — это список, значения которого соответствуют \$(x,y)\$.
Использует уравнение \$y=\sqrt{\frac{x^2-1}{n}}\$ для \$x\ge2\$ для вычисления фундаментального решения.

Текущая пара \$(x,y)\$ для этого уравнения является фундаментальным решением тогда и только тогда, когда \$y\bmod1=0\$.

Примеры:

Объяснение: Примечание: TI-BASIC — это токенизированный язык. Количество символов делает нет

Попробуйте онлайн!

Объяснение

Код продолжает увеличивать счетчик к = 1, 2, 3, ... Для каждого к, решения х, й с 1 ≤ х ≤ к, 1 ≤ й ≤ к разыскиваются. Процесс, когда какое-то решение найдено.

Эта процедура гарантированно находит только одно решение, причем именно фундаментальное. Чтобы понять, почему, обратите внимание, что

1. Любое решение х>0, й>0 для н>1 удовлетворяет х>й.
2. Если х,й это решение и х',й' это другое решение, тогда обязательно х≠х' и й≠й'.

Как следствие 1 и 2,

• Когда процедура останавливается на заданном к, только один решение для этого существует к, ведь если бы решений было два, одно из них было бы найдено раньше, и процесс остановился бы при меньшем к.
• Это решение является фундаментальным, потому что, опять же, если бы существовало решение с меньшими х его нашли бы раньше.

Питон 2, 49 байт

Попробуйте онлайн!

Находки x.0y as the smallest number above 1 where ökî²*)_°▼Þ√î . Затем находит ḟΛ¤ȯ=→*⁰□π2N Input is n, accessed through ⁰. N Natural numbers: [1,2,3,4,.. π2 2-tuples, ordered by sum: [[1,1],[1,2],[2,1],[1,3],[2,2],.. ḟ Find the first that satisfies this: Λ All adjacent pairs x,y satisfy this: ¤ □ Square both: x²,y² ȯ *⁰ Multiply second number by n: x²,ny² → Increment second number: x²,ny²+1 = These are equal. from ḟΛ¤ȯ=→*⁰□π2N как x, y .

Хаскелл, 46 байт

Простой поиск методом грубой силы. При этом используется тот факт, что фундаментальное решение \$(x,y)\$, удовлетворяющее \$x^2 - ny^2 = 1 \$, должно иметь \$y \leq x\$.

Попробуйте онлайн!

C# (интерактивный компилятор Visual C#), 70 69 байт

Порт мой ответ на Java 8, но выводит кортеж вместо строки для экономии байтов.

Попробуйте онлайн.

Желе, 15 байт

Попробуйте онлайн!

Полная программа, принимающая один аргумент f n=[(x,y)|x<-[1..],y<-[1..x],x^2-n*y^2==1]!!0 and returns a tuple of y = floor(x / sqrt(n)) .

Шелуха, 12 байт

Попробуйте онлайн!

Объяснение

МатематикаГольф, 12 байт

Попробуйте онлайн!

Когда дело доходит до форматирования вывода, я выражаю благодарность «Радуйся, Мария». Если это запрещено, у меня есть решение на 1 байт длиннее. Выходной формат: x , where a=input()**.5 x=2 while x%a*x>1:x+=1 print x,x//a является разделителем между двумя числами.

Объяснение

Я черпал вдохновение из ответа Эмигны 05AB1E, но смог найти некоторые улучшения. Если выбранный мной разделитель недопустим, добавьте пробел перед последним байтом, чтобы количество байтов было равно 13.

APL(NARS), 906 байт

Выше есть две функции: функция sqrti, которая находит квадратный корень пола, и функция pell, возвращающая Zilde об ошибке и основанная на чтении страницы. http://mathworld.wolfram.com/PellEquation.html он будет использовать алгоритм для знания sqrt числа, продолжая дробь (даже если я использую один алгоритм для знания sqrt, используя

метод Ньютона) и остановится, когда найдет p и q такие, что

Тест:

, 53 байта

Попробуйте онлайн! ПортКевин Круйссен

Пиф, 15 байт Попробуйте онлайнздесь n=>[(g=x=>(y=(x/n)**.5)%1?1+g(x+=k+=2):2)(k=3),y] then n=>(g=x=>(y=((x*x-1)/n)**.5)%1?g(x+1):[x,y])(2) . Выход:

½©%1İ$<®‘¤$п¹;Ḋ$LḂ$?Ḟ?@ṫ-ṚZæ.ʋ¥ƒØ.,U¤-ị is the 3-byte Unicode character #221A. Outputs the solution in the order (y,x) instead of (x,y). As usual with the imperfect n=scan();while((x=(1+n*T^2)^.5)%%1)T=T+1;x;+T , 41 байт n->{ // Method with double parameter and string return-type int x=1; // Integer `x`, starting at 1 var y=.1; // Double `y`, starting at 0.1 for(;y%1>0;) // Loop as long as `y` contains decimal digits: y= // Set `y` to: Math.sqrt( // The square-root of: -x* // Negative `x`, multiplied by ~++x // `(-x-2)` (or `-(x+1)-1)` to be exact) // (because we increase `x` by 1 first with `++x`) /n); // Divided by the input return x+" "+y;} // After the loop, return `x` and `y` with space-delimiter as result is at most 65538.

и его ограниченные итерации работают только на входных данных, где истинное значение

, 45 байт

Попробуйте онлайн! ∞ # from the infinite list of numbers [1 ...] .Δ } # find the first number that returns true under n # square * # multiply with input > # increment t© # sqrt (and save to register as potential x) 1% # modulus 1 _ # logical negation ®‚ # pair result (y) with register (x) upwards, with ∞.Δn*>t©1%_}®‚ Алгоритм перебора, поиск из [y, x] when FindInstance[x^2-y^2#==1&&x>1,{x,y},Integers]& и уменьшаясь в каждом цикле, увеличивая n->(a=quadunit(4*n))*a^(norm(a)<0) followed by w достигает 0. Выходной сигнал

, 69 байт

, 75 байт

Попробуйте онлайн!

Объяснение Грубая сила. Использование $$x определенный верхний предел фундаментального решения уравнения Пелля

Имея неограниченное время и память, можно было бы использовать понимание списка вместо итератора и сохранить 3 байта следующим образом:Питон 3

, 72 байта

, 64 байта

Попробуйте онлайн! ;1↔;Ċz×ᵐ-1∧Ċ√ᵐℕᵐ .