Решить уравнение.

и задачки для интервью.
[xyz]
Новичок
Posts: 51
Joined: 30 Sep 2018 03:35

Решить уравнение.

Post by [xyz] »

Image

Наити первое решение уравнения в натуральных числах для х и у, когда х > 10000.
Last edited by [xyz] on 07 Jan 2021 22:50, edited 1 time in total.
User avatar
jsjs
Уже с Приветом
Posts: 19484
Joined: 09 Aug 2009 03:46
Location: Москва->США

Re: Решить уравнение.

Post by jsjs »

Видимо, в натуральных числах?

x=14841
y=25705
蝸牛そろそろ登れ富士の山
User avatar
veey+
Уже с Приветом
Posts: 2198
Joined: 29 Jul 2019 17:34
Location: Нуёкщина -> Притампье

Re: Решить уравнение.

Post by veey+ »

перебором решили? :mrgreen:
This world is totally fugazi.
[xyz]
Новичок
Posts: 51
Joined: 30 Sep 2018 03:35

Re: Решить уравнение.

Post by [xyz] »

jsjs wrote: 07 Jan 2021 21:10 Видимо, в натуральных числах?

x=14841
y=25705
Спасибо за поправку. Да - это в натуральных числах. Ответ точный ! :D
User avatar
jsjs
Уже с Приветом
Posts: 19484
Joined: 09 Aug 2009 03:46
Location: Москва->США

Re: Решить уравнение.

Post by jsjs »

veey+ wrote: 07 Jan 2021 22:02 перебором решили? :mrgreen:
Естественно. Protiv loma net priyoma. На обычном лаптопе с Матлабом вот этот код исполняется за 3 секунды:

biden=10000;
for x=10001:50000
for y=10001:50000
harris=abs(3*x*(x-1)/(y*(y-1))-1);
if abs(harris)<biden
biden=harris;
fprintf('%5d %5d %30.20f\n',x,y,biden);
end
end
end
蝸牛そろそろ登れ富士の山
[xyz]
Новичок
Posts: 51
Joined: 30 Sep 2018 03:35

Re: Решить уравнение.

Post by [xyz] »

jsjs wrote: Protiv loma net priyoma.
И всё-таки «есть приём против лома».
jsjs попробуйте решить для х > 1 000 000 000 000 000 (10^15)
User avatar
jsjs
Уже с Приветом
Posts: 19484
Joined: 09 Aug 2009 03:46
Location: Москва->США

Re: Решить уравнение.

Post by jsjs »

[xyz] wrote: 08 Jan 2021 01:02
jsjs wrote: Protiv loma net priyoma.
И всё-таки «есть приём против лома».
jsjs попробуйте решить для х > 1 000 000 000 000 000 (10^15)
В подлиннике -- "против лома нет приёма если нет другого лома" :-)
蝸牛そろそろ登れ富士の山
User avatar
jsjs
Уже с Приветом
Posts: 19484
Joined: 09 Aug 2009 03:46
Location: Москва->США

Re: Решить уравнение.

Post by jsjs »

x=1,092,576,704,233,581
Image
蝸牛そろそろ登れ富士の山
[xyz]
Новичок
Posts: 51
Joined: 30 Sep 2018 03:35

Re: Решить уравнение.

Post by [xyz] »

:-) :-) :-)
User avatar
jsjs
Уже с Приветом
Posts: 19484
Joined: 09 Aug 2009 03:46
Location: Москва->США

Re: Решить уравнение.

Post by jsjs »

Немного о химической структуре лома.

На том же Матлабе за несколько минут кодом

biden=10000;
for x=1:1000000
for y=1:1000000
harris=3*x^2-3*x-y^2-y;
if harris==0
fprintf('%10d %10d \n',x,y);
end
end
end

получаем результаты вида

2 2
6 9
21 35
77 132
286 494
1066 1845
3977 6887
14841 25704
55386 95930
206702 358017

Далее смотрим за соотношением x(n+1)/x(n) и наблюдаем, что оно достаточно быстро сходится к чему-то типа 3.73202614379085

По взгляду на цифирки ясно, что это просто
2+sqrt(3)=3.732050807568877

Стало быть, скорее всего, иксы описываются какой-то рекуррентной последовательностью, где
2+sqrt(3) -- наибольший корень соответствующего характеристического многочлена.

Далее, подбираем коэффициенты многочлена и убеждаемся, что рекуррентная последовательность вида
x(n)=5x(n-1)-5x(n-2)+x(n-3)
работает на всех полученных результатах. А это, в свою очередь, формирует базис индукции, после чего в лоб переносится на следующие члены.
蝸牛そろそろ登れ富士の山
[xyz]
Новичок
Posts: 51
Joined: 30 Sep 2018 03:35

Re: Решить уравнение.

Post by [xyz] »

jsjs - Молодец !!!
User avatar
Гоша Хороший
Мистер Привет 2018
Posts: 1853
Joined: 03 Dec 2017 20:31
Location: 3.14ter -> 1qver

Re: Решить уравнение.

Post by Гоша Хороший »

формулу можно получить аналитически. те же квадратные уравнения (8-класс)

3(x^2-x) = y^2-y
если числа натуральные, то
y=x+N
получим
2x^2-2(1+N)x-N(N-1)=0
a=2; b=-2(1+N); c=-N(N-1);
D=4(3N^2+1)
x=(1+N+sqrt(3N^2+1))/2

если N=1, то х=2 и y=3. это 1-е решение
если N>1000, N=10864, то x=14841, y=25705
и т.д

но перебор нужен (числитель должен быть четным)
Гоша хороший, а Маша еще лучше
User avatar
jsjs
Уже с Приветом
Posts: 19484
Joined: 09 Aug 2009 03:46
Location: Москва->США

Re: Решить уравнение.

Post by jsjs »

Формула для n-go члена последовательности x(n) в явном виде, без перебора и без рекуррентности:

x(n)=(6+(3+biden)*(2+biden)^(n-1) + (3-biden)*(2-biden)^(n-1))/12,

где biden=sqrt(3).
蝸牛そろそろ登れ富士の山
User avatar
kyk
Уже с Приветом
Posts: 31589
Joined: 21 Nov 2004 05:12
Location: камбуз на кампусе

Re: Решить уравнение.

Post by kyk »

jsjs wrote: 08 Jan 2021 03:55 x=1,092,576,704,233,581
предложИте Бидену свои услуги :good:
Лучше переесть, чем недоспать! © Обратное тоже верно :umnik1:
User avatar
jsjs
Уже с Приветом
Posts: 19484
Joined: 09 Aug 2009 03:46
Location: Москва->США

Re: Решить уравнение.

Post by jsjs »

kyk wrote: 10 Jan 2021 02:41
jsjs wrote: 08 Jan 2021 03:55 x=1,092,576,704,233,581
предложИте Бидену свои услуги :good:
"В Красной Армии штыки чай найдутся, без тебя большевики обойдутся"
蝸牛そろそろ登れ富士の山

Return to “Головоломки”