-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path066.py
1093 lines (1084 loc) · 12.1 KB
/
066.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
'''
ISSO FUNCIONA ... MAS TA MUITO DEMORADO!
Project Euler - Problem 66
Consider quadratic Diophantine equations of the form:
x^2 - D * y^2 = 1
For example, when D=13, the minimal solution in x is 649^2 - 13 * 180^2 = 1.
It can be assumed that there are no solutions in positive integers when D is square.
By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we obtain the following:
3^2 - 2*2^2 = 1
2^2 - 3*1^2 = 1
9^2 - 5*4^2 = 1
5^2 - 6*2^2 = 1
8^2 - 7*3^2 = 1
Hence, by considering minimal solutions in x for D = 7, the largest x is obtained when D=5.
Find the value of D = 1000 in minimal solutions of x for which the largest value of x is obtained
'''
'''
def solveQuadDiophantine(D, maxIter):
# for x, y, n and D integers,
# finds the minimum x such that:
# x**2 - D.y**2 = 1
# there's no solution if D=n**2
if D**0.5 == int(D**0.5):
return -1
y=1
iter=0
while True:
diopSqrd = 1+D*y**2
diopFloat = int(round(diopSqrd**0.5))
diopSqrdInt = diopFloat**2
if diopSqrd == diopSqrdInt:
break
y+=1
iter+=1
if iter>maxIter: return 0
return int(diopFloat)
'''
def solveQuadDiophantine(D, maxIter=1000):
# for x, y, n and D integers,
# finds the minimum x such that:
# x**2 - D.y**2 = 1
# there's no solution if D=n**2
#
# note that x**2 = 1 + D * y**2
# hence, minimise y will
# also minimise x
#
if D**0.5 == int(D**0.5):
return -1
y=1
iter=0
while True:
x = (1.0+D*y**2)**0.5
if x == int(round(x)):
break
else:
x = int(x)+1
y = ((x**2-1.0)/D)**0.5
if y == int(round(y)):
break
y = int(y)+1
iter+=1
#print x,y
if iter>maxIter: return 0
return int(x)
###################################
Dmax=xmax=0
Dunsolved=[]
for D in range(509, 1000):
x=solveQuadDiophantine(D,100000)
if x==0:
Dunsolved.append(D)
print(D, x)
if x>xmax:
xmax=x
Dmax=D
print(Dmax)
print("unsolved", len(Dunsolved))
'''
ja rodei ate o 500-e-poucos:
1 -1
2 3
3 2
4 -1
5 9
6 5
7 8
8 3
9 -1
10 19
11 10
12 7
13 649
14 15
15 4
16 -1
17 33
18 17
19 170
20 9
21 55
22 197
23 24
24 5
25 -1
26 51
27 26
28 127
29 9801
30 11
31 1520
32 17
33 23
34 35
35 6
36 -1
37 73
38 37
39 25
40 19
41 2049
42 13
43 3482
44 199
45 161
46 24335
47 48
48 7
49 -1
50 99
51 50
52 649
53 66249
54 485
55 89
56 15
57 151
58 19603
59 530
60 31
61 335159612
62 63
63 8
64 -1
65 129
66 65
67 48842
68 33
69 7775
70 251
71 3480
72 17
73 2281249
74 3699
75 26
76 57799
77 351
78 53
79 80
80 9
81 -1
82 163
83 82
84 55
85 285769
86 10405
87 28
88 197
89 500001
90 19
91 1574
92 1151
93 12151
94 2143295
95 39
96 49
97 62809633
98 99
99 10
100 -1
101 201
102 101
103 227528
104 51
105 41
106 32080051
107 962
108 1351
109 181718045
110 21
111 295
112 127
113 1204353
114 1025
115 1126
116 9801
117 649
118 306917
119 120
120 11
121 -1
122 243
123 122
124 4620799
125 930249
126 449
127 4730624
128 577
129 16855
130 6499
131 10610
132 23
133 2588599
134 145925
135 244
136 35
137 6083073
138 47
139 77563250
140 71
141 95
142 143
143 12
144 -1
145 289
146 145
147 97
148 73
149 255105526
150 49
151 233961551
152 37
153 2177
154 21295
155 249
156 25
157 241895480
158 7743
159 1324
160 721
161 11775
162 19601
163 64080026
164 2049
165 1079
166 197136773
167 168
168 13
169 -1
170 339
171 170
172 24248647
173 2499849
174 1451
175 2024
176 199
177 62423
178 1601
179 4190210
180 161
181 401010423
182 27
183 487
184 24335
185 9249
186 7501
187 1682
188 4607
189 55
190 52021
191 8994000
192 97
193 391883492
194 195
195 14
196 -1
197 393
198 197
199 555941316
200 99
201 515095
202 19731763
203 57
204 4999
205 39689
206 59535
207 1151
208 649
209 46551
210 29
211 291226557
212 66249
213 194399
214 426950027
215 44
216 485
217 3844063
218 126003
219 74
220 89
221 1665
222 149
223 224
224 15
225 -1
226 451
227 226
228 151
229 5848201
230 91
231 76
232 19603
233 283475737
234 5201
235 46
236 561799
237 228151
238 11663
239 6195120
240 31
241 142022136
242 19601
243 70226
244 425680601
245 51841
246 88805
247 85292
248 63
249 8553815
250 39480499
251 3674890
252 127
253 303010724
254 255
255 16
256 -1
257 513
258 257
259 847225
260 129
261 192119201
262 104980517
263 139128
264 65
265 73738369
266 685
267 2402
268 534917633
269 13449
270 5291
271 667137236
272 33
273 727
274 3959299
275 199
276 7775
277 567444389
278 2501
279 1520
280 251
281 606183385
282 2351
283 138274082
284 24220799
285 2431
286 561835
287 288
288 17
289 -1
290 579
291 290
292 2281249
293 12320649
294 4801
295 2024999
296 3699
297 48599
298 268665646
299 415
300 1351
301 517335023
302 4276623
303 2524
304 57799
305 489
306 35
307 88529282
308 351
309 440045063
310 848719
311 16883880
312 53
313 126862368
314 392499
315 71
316 12799
317 514816725
318 107
319 12901780
320 161
321 215
322 323
323 18
324 -1
325 649
326 325
327 217
328 163
329 2376415
330 109
331 717616116
332 13447
333 73
334 587510696
335 604
336 55
337 363218969
338 114243
339 97970
340 285769
341 10626551
342 37
343 130576328
344 10405
345 6761
346 17299
347 641602
348 1567
349 169648201
350 449
351 62425
352 77617
353 366866809
354 258065
355 954809
356 500001
357 3401
358 397531772
359 360
360 19
361 -1
362 723
363 362
364 4954951
365 23915529
366 907925
367 605024944
368 1151
369 8396801
370 213859
371 1695
372 12151
373 52387849
374 3365
375 15124
376 2143295
377 233
378 8749
379 568796915
380 39
381 1015
382 174663166
383 18768
384 4801
385 95831
386 111555
387 3482
388 62809633
389 3287049
390 79
391 7338680
392 99
393 46437143
394 335545697
395 159
396 199
397 474379627
398 399
399 20
400 -1
401 801
402 401
403 669878
404 201
405 161
406 59468095
407 2663
408 101
409 445055861
410 81
411 49730
412 434122470
413 113399
414 24335
415 18412804
416 5201
417 85322647
418 33857
419 270174970
420 41
421 378867518
422 7022501
423 4607
424 32080051
425 143649
426 88751
427 62
428 1850887
429 1524095
430 2862251
431 151560720
432 1351
433 312800069
434 125
435 146
436 181718045
437 4599
438 293
439 440
440 21
441 -1
442 883
443 442
444 295
445 43468489
446 110166015
447 148
448 127
449 189471332
450 19601
451 46471490
452 1204353
453 1653751
454 650308390
455 64
456 1025
457 583531623
458 22899
459 499850
460 2535751
461 984014171
462 43
463 334453558
464 9801
465 15871
466 387494822
467 1625626
468 649
469 137215
470 1691
471 7838695
472 306917
473 87
474 193549
475 57799
476 28799
477 368477069
478 801567695
479 2989440
480 241
481 549668033
482 483
483 22
484 -1
485 969
486 485
487 317492291
488 243
489 707974023
490 1039681
491 386467032
492 29767
493 455568981
494 73035
495 89
496 4620799
497 1201887
498 179777
499 4490
500 930249
501 673773097
502 622774517
503 24648
504 449
505 809
506 45
507 1351
508 320775491
509 395727950
510 271
511 659810024
512 665857
513 13771351
514 4625
515 17406
516 16855
517 111788327
518 2367
519 14851876
520 6499
521 128377240
522 19603
523 399007848
524 225144199
525 6049
526 505498477
527 528
528 23
529 -1
530 1059
531 530
532 2588599
533 74859849
534 3678725
535 1618804
536 145925
537 192349463
538 246650288
539 3970
540 119071
541 503425738
542 4293183
543 669337
544 2449
545 1961
546 701
547 293546453
548 6083073
549 244638623
550 30580901
551 8380
552 47
553 635797691
554 443054383
555 1814
556 155126500
557 27849
558 7937
559 506568295
560 71
561 522785
562 220938497
563 68122
564 95
565 689960039
566 95609285
567 2024
568 143
569 423458123
570 191
571 406819973
572 287
573 383
574 575
575 24
576 -1
577 1153
578 577
579 385
580 289
581 532576276
582 193
583 8429543
584 145
585 33281
586 547586916
587 1907162
588 97
589 687148095
590 5781
591 165676
592 73
593 497309513
594 1098305
595 18514
596 510211052
597 1032014507
598 1574351
599 486663193
600 49
601 529479983
602 687
603 48842
604 467923102
605 930249
606 42187499
607 548871575
608 2737
609 605695
610 599778188
611 236926
612 2177
613 588084296
614 263218868
615 124
616 21295
617 1592796237
618 10093
619 675920981
620 249
621 7775
622 293024624
623 624
624 25
625 -1
626 1251
627 626
628 483790960
629 123245001
630 251
631 560155918
632 7743
633 440772247
634 336046992
635 126
636 3505951
637 200477279
638 42283
639 24220799
640 1039681
641 162122886
642 5777
643 393427068
644 11775
645 1024001
646 305
647 120187368
648 19601
649 339283364
649 339283364
650 51
651 1735
652 897120364
653 246838808
654 8915765
655 437437795
656 2049
657 2281249
658 1693
659 5930
660 1079
661 391044982
662 464986126
663 103
664 394273546
665 13719
666 27365201
667 107119097
668 56447
669 146079351
670 5791211
671 58620
672 337
673 958168334
674 675
675 26
676 -1
677 1353
678 677
679 663877522
680 339
681 489307679
682 1197901
683 170067682
684 57799
685 218623878
686 455613205
687 165337
688 24248647
689 105
690 1471
691 388834592
692 2499849
693 246401
694 563935873
695 33639
696 1451
697 34849
698 51999603
699 2271050
700 8193151
701 277631049
702 53
703 1159172
704 79201
705 237161
706 34595
707 2526
708 62423
709 905460983
710 1279
711 80
712 1601
713 5286367
714 4115
715 75646
716 335791967
717 6998399
718 544239212
719 545019485
720 161
721 255367616
722 22619537
723 242
724 401010423
725 9801
726 485
727 728
728 27
729 -1
730 1459
731 730
732 487
733 195307849
734 10394175
735 244
736 24335
737 252975383
738 163
739 620125683
740 9249
741 7352695
742 263091151
743 714024
744 7501
745 12769001
746 606762705
747 82
748 5658247
749 502719069
750 2550251
751 589999787
752 4607
753 423135340
754 836977699
755 1209
756 55
757 150663196
758 413959717
759 551
760 52021
761 1280001
762 6349
763 271728688
764 250215553
765 285769
766 363798414
767 31212
768 18817
769 570214728
770 111
771 494900135
772 783766984
773 373378327
774 10405
775 4620799
776 195
777 223
778 1905497077
779 11785490
780 391
781 67606199
782 783
783 28
784 -1
785 1569
786 785
787 584659685
788 393
789 275779551
790 248447827
791 225
792 197
793 4393
794 325449512
795 6626
796 1111882632
797 1216797167
798 113
799 424
800 19601
801 650973651
802 295496099
803 7226
804 515095
805 386225097
806 6166395
807 51841948
808 19731763
809 278601383
810 27379
811 306799399
812 57
813 2167
814 548663137
815 156644
816 4999
817 343
818 40899
819 1574
820 39689
821 262083723
822 7397
823 548657093
824 59535
825 48599
826 615591509
827 900602
828 1151
829 879672881
830 146411
831 9799705
832 842401
833 9478657
834 579749836
835 553153089
836 46551
837 12151
838 576238683
839 840
840 29
841 -1
842 1683
843 842
844 582453114
845 299537289
846 2143295
847 8193151
848 66249
849 888102911
850 2449
851 8418574
852 194399
853 716385636
854 1294299
855 3041
856 622103357
857 473105997
858 703
859 442140817
860 3871
861 541601801
862 713551220
863 275881016
864 470449
865 348345108
866 42435
867 70226
868 3844063
869 291842773
870 59
871 494202326
872 126003
873 62809633
874 3725
875 120126
876 10951
877 628901390
878 9314703
879 107245324
880 89
881 407030946
882 19601
883 1025661481
884 1665
885 119
886 519758729
887 469224
888 149
889 257057147
890 179
891 3970
892 100351
893 394997639
894 299
895 359
896 449
897 599
898 899
899 30
900 -1
901 1801
902 901
903 601
904 451
905 361
906 301
907 266874460
908 102151
909 80801
910 181
911 551326625