# Math Help - Integer Solutions?

1. Thanks for the information about pari/gp. I wish I had the time to take a look at it.
I've modified my k=4 solution finding program and it is now about *3 faster on my machine.
As I'm currently only searching for fairly small solutions I've built a table of squares up front, so all the multiplications in the outer loops disappear.

2. ## Raw Data

Hey guys, I found some more... If you just copy/paste the text below you should be able to put it in a spreadsheet easily enough. I'll post again with a run-through of my search algorithm.

67405=1*1*5*13*17*61=227^2+126^2=218^2+141^2=189^2 +178^2=237^2+106^2 and (227*126)^2+(218*141)^2=(189*178)^2+(237*106)^2
600445=1*1*5*29*41*101=613^2+474^2=773^2+54^2=683^ 2+366^2=206^2+747^2 and (613*474)^2+(773*54)^2=(683*366)^2+(206*747)^2
55445869=1*1*37*37*101*401=1110^2+7363^2=3438^2+66 05^2=2062^2+7155^2=6915^2+2762^2 and (1110*7363)^2+(3438*6605)^2=(2062*7155)^2+(6915*27 62)^2
242048509=1*1*53*73*73*857=14853^2+4630^2=14090^2+ 6597^2=8478^2+13045^2=15403^2+2190^2 and (14853*4630)^2+(14090*6597)^2=(8478*13045)^2+(1540 3*2190)^2
5915065=1*5*13*17*53*101=2076^2+1267^2=2428^2+141^ 2=2324^2+717^2=2253^2+916^2 and (2076*1267)^2+(2428*141)^2=(2324*717)^2+(2253*916) ^2
81524605=1*5*17*41*149*157=8498^2+3051^2=8629^2+26 58^2=7947^2+4286^2=9003^2+686^2 and (8498*3051)^2+(8629*2658)^2=(7947*4286)^2+(9003*68 6)^2
532946005=1*5*17*53*281*421=19598^2+12201^2=20583^ 2+10454^2=21366^2+8743^2=17769^2+14738^2 and (19598*12201)^2+(20583*10454)^2=(21366*8743)^2+(17 769*14738)^2
166045477=1*13*17*61*109*113=12606^2+2671^2=10609^ 2+7314^2=12351^2+3674^2=11199^2+6374^2 and (12606*2671)^2+(10609*7314)^2=(12351*3674)^2+(1119 9*6374)^2
1685125=5*5*5*13*17*61=1135^2+630^2=1090^2+705^2=9 45^2+890^2=1185^2+530^2 and (1135*630)^2+(1090*705)^2=(945*890)^2+(1185*530)^2
15011125=5*5*5*29*41*101=3065^2+2370^2=3865^2+270^ 2=3415^2+1830^2=1030^2+3735^2 and (3065*2370)^2+(3865*270)^2=(3415*1830)^2+(1030*373 5)^2
1386146725=5*5*37*37*101*401=5550^2+36815^2=17190^ 2+33025^2=10310^2+35775^2=34575^2+13810^2 and (5550*36815)^2+(17190*33025)^2=(10310*35775)^2+(34 575*13810)^2
6051212725=5*5*53*73*73*857=74265^2+23150^2=70450^ 2+32985^2=42390^2+65225^2=77015^2+10950^2 and (74265*23150)^2+(70450*32985)^2=(42390*65225)^2+(7 7015*10950)^2
11391445=5*13*13*13*17*61=2951^2+1638^2=2834^2+183 3^2=2457^2+2314^2=3081^2+1378^2 and (2951*1638)^2+(2834*1833)^2=(2457*2314)^2+(3081*13 78)^2
101475205=5*13*13*29*41*101=2678^2+9711^2=8879^2+4 758^2=10049^2+702^2=7969^2+6162^2 and (2678*9711)^2+(8879*4758)^2=(10049*702)^2+(7969*61 62)^2
19480045=5*13*17*17*17*61=3859^2+2142^2=3706^2+239 7^2=3213^2+3026^2=4029^2+1802^2 and (3859*2142)^2+(3706*2397)^2=(3213*3026)^2+(4029*18 02)^2
56687605=5*13*17*29*29*61=6583^2+3654^2=6322^2+408 9^2=5481^2+5162^2=6873^2+3074^2 and (6583*3654)^2+(6322*4089)^2=(5481*5162)^2+(6873*30 74)^2
92277445=5*13*17*37*37*61=8399^2+4662^2=8066^2+521 7^2=6993^2+6586^2=8769^2+3922^2 and (8399*4662)^2+(8066*5217)^2=(6993*6586)^2+(8769*39 22)^2
113307805=5*13*17*41*41*61=9307^2+5166^2=8938^2+57 81^2=7749^2+7298^2=9717^2+4346^2 and (9307*5166)^2+(8938*5781)^2=(7749*7298)^2+(9717*43 46)^2
189340645=5*13*17*53*53*61=12031^2+6678^2=11554^2+ 7473^2=10017^2+9434^2=12561^2+5618^2 and (12031*6678)^2+(11554*7473)^2=(10017*9434)^2+(1256 1*5618)^2
250814005=5*13*17*61*61*61=13847^2+7686^2=13298^2+ 8601^2=11529^2+10858^2=14457^2+6466^2 and (13847*7686)^2+(13298*8601)^2=(11529*10858)^2+(144 57*6466)^2
359201245=5*13*17*61*73*73=16571^2+9198^2=15914^2+ 10293^2=13797^2+12994^2=17301^2+7738^2 and (16571*9198)^2+(15914*10293)^2=(13797*12994)^2+(17 301*7738)^2
687598405=5*13*17*61*101*101=22927^2+12726^2=22018 ^2+14241^2=19089^2+17978^2=23937^2+10706^2 and (22927*12726)^2+(22018*14241)^2=(19089*17978)^2+(2 3937*10706)^2
800838805=5*13*17*61*109*109=24743^2+13734^2=23762 ^2+15369^2=20601^2+19402^2=25833^2+11554^2 and (24743*13734)^2+(23762*15369)^2=(20601*19402)^2+(2 5833*11554)^2
860694445=5*13*17*61*113*113=25651^2+14238^2=24634 ^2+15933^2=21357^2+20114^2=26781^2+11978^2 and (25651*14238)^2+(24634*15933)^2=(21357*20114)^2+(2 6781*11978)^2
1496458405=5*13*17*61*149*149=33823^2+18774^2=3248 2^2+21009^2=28161^2+26522^2=35313^2+15794^2 and (33823*18774)^2+(32482*21009)^2=(28161*26522)^2+(3 5313*15794)^2
1661465845=5*13*17*61*157*157=35639^2+19782^2=3422 6^2+22137^2=29673^2+27946^2=37209^2+16642^2 and (35639*19782)^2+(34226*22137)^2=(29673*27946)^2+(3 7209*16642)^2
5322366205=5*13*17*61*281*281=63787^2+35406^2=6125 8^2+39621^2=53109^2+50018^2=66597^2+29786^2 and (63787*35406)^2+(61258*39621)^2=(53109*50018)^2+(6 6597*29786)^2
10838791405=5*13*17*61*401*401=91027^2+50526^2=874 18^2+56541^2=75789^2+71378^2=95037^2+42506^2 and (91027*50526)^2+(87418*56541)^2=(75789*71378)^2+(9 5037*42506)^2
11946929605=5*13*17*61*421*421=95567^2+53046^2=917 78^2+59361^2=79569^2+74938^2=99777^2+44626^2 and (95567*53046)^2+(91778*59361)^2=(79569*74938)^2+(9 9777*44626)^2
49505534845=5*13*17*61*857*857=194539^2+107982^2=1 86826^2+120837^2=161973^2+152546^2=203109^2+90842^ 2 and (194539*107982)^2+(186826*120837)^2=(161973*152546 )^2+(203109*90842)^2
173528605=5*17*17*29*41*101=10421^2+8058^2=13141^2 +918^2=11611^2+6222^2=3502^2+12699^2 and (10421*8058)^2+(13141*918)^2=(11611*6222)^2+(3502* 12699)^2
504974245=5*29*29*29*41*101=17777^2+13746^2=22417^ 2+1566^2=19807^2+10614^2=5974^2+21663^2 and (17777*13746)^2+(22417*1566)^2=(19807*10614)^2+(59 74*21663)^2
822009205=5*29*37*37*41*101=22681^2+17538^2=28601^ 2+1998^2=25271^2+13542^2=7622^2+27639^2 and (22681*17538)^2+(28601*1998)^2=(25271*13542)^2+(76 22*27639)^2
1009348045=5*29*41*41*41*101=25133^2+19434^2=31693 ^2+2214^2=28003^2+15006^2=8446^2+30627^2 and (25133*19434)^2+(31693*2214)^2=(28003*15006)^2+(84 46*30627)^2
1686650005=5*29*41*53*53*101=32489^2+25122^2=40969 ^2+2862^2=36199^2+19398^2=10918^2+39591^2 and (32489*25122)^2+(40969*2862)^2=(36199*19398)^2+(10 918*39591)^2
2234255845=5*29*41*61*61*101=37393^2+28914^2=47153 ^2+3294^2=41663^2+22326^2=12566^2+45567^2 and (37393*28914)^2+(47153*3294)^2=(41663*22326)^2+(12 566*45567)^2
3199771405=5*29*41*73*73*101=44749^2+34602^2=56429 ^2+3942^2=49859^2+26718^2=15038^2+54531^2 and (44749*34602)^2+(56429*3942)^2=(49859*26718)^2+(15 038*54531)^2
6125139445=5*29*41*101*101*101=61913^2+47874^2=780 73^2+5454^2=68983^2+36966^2=20806^2+75447^2 and (61913*47874)^2+(78073*5454)^2=(68983*36966)^2+(20 806*75447)^2
7133887045=5*29*41*101*109*109=66817^2+51666^2=842 57^2+5886^2=74447^2+39894^2=81423^2+22454^2 and (66817*51666)^2+(84257*5886)^2=(74447*39894)^2+(81 423*22454)^2
7667082205=5*29*41*101*113*113=69269^2+53562^2=873 49^2+6102^2=77179^2+41358^2=84411^2+23278^2 and (69269*53562)^2+(87349*6102)^2=(77179*41358)^2+(84 411*23278)^2
13330479445=5*29*41*101*149*149=91337^2+70626^2=11 5177^2+8046^2=101767^2+54534^2=111303^2+30694^2 and (91337*70626)^2+(115177*8046)^2=(101767*54534)^2+( 111303*30694)^2
14800368805=5*29*41*101*157*157=96241^2+74418^2=12 1361^2+8478^2=107231^2+57462^2=117279^2+32342^2 and (96241*74418)^2+(121361*8478)^2=(107231*57462)^2+( 117279*32342)^2
47411737645=5*29*41*101*281*281=172253^2+133194^2= 217213^2+15174^2=191923^2+102846^2=209907^2+57886^ 2 and (172253*133194)^2+(217213*15174)^2=(191923*102846) ^2+(209907*57886)^2
96552156445=5*29*41*101*401*401=245813^2+190074^2= 309973^2+21654^2=273883^2+146766^2=82606^2+299547^ 2 and (245813*190074)^2+(309973*21654)^2=(273883*146766) ^2+(82606*299547)^2
106423472245=5*29*41*101*421*421=258073^2+199554^2 =325433^2+22734^2=287543^2+154086^2=314487^2+86726 ^2 and (258073*199554)^2+(325433*22734)^2=(287543*154086) ^2+(314487*86726)^2
440996229805=5*29*41*101*857*857=525341^2+406218^2 =662461^2+46278^2=585331^2+313662^2=176542^2+64017 9^2 and (525341*406218)^2+(662461*46278)^2=(585331*313662) ^2+(176542*640179)^2
9370351861=13*13*37*37*101*401=14430^2+95719^2=446 94^2+85865^2=26806^2+93015^2=89895^2+35906^2 and (14430*95719)^2+(44694*85865)^2=(26806*93015)^2+(8 9895*35906)^2
40906198021=13*13*53*73*73*857=193089^2+60190^2=18 3170^2+85761^2=110214^2+169585^2=200239^2+28470^2 and (193089*60190)^2+(183170*85761)^2=(110214*169585)^ 2+(200239*28470)^2
16023856141=17*17*37*37*101*401=18870^2+125171^2=5 8446^2+112285^2=35054^2+121635^2=117555^2+46954^2 and (18870*125171)^2+(58446*112285)^2=(35054*121635)^2 +(117555*46954)^2
69952019101=17*17*53*73*73*857=252501^2+78710^2=23 9530^2+112149^2=144126^2+221765^2=261851^2+37230^2 and (252501*78710)^2+(239530*112149)^2=(144126*221765) ^2+(261851*37230)^2
46629975829=29*29*37*37*101*401=32190^2+213527^2=9 9702^2+191545^2=59798^2+207495^2=200535^2+80098^2 and (32190*213527)^2+(99702*191545)^2=(59798*207495)^2 +(200535*80098)^2
203562796069=29*29*53*73*73*857=430737^2+134270^2= 408610^2+191313^2=245862^2+378305^2=446687^2+63510 ^2 and (430737*134270)^2+(408610*191313)^2=(245862*378305 )^2+(446687*63510)^2
75905394661=37*37*37*37*101*401=41070^2+272431^2=1 27206^2+244385^2=76294^2+264735^2=255855^2+102194^ 2 and (41070*272431)^2+(127206*244385)^2=(76294*264735)^ 2+(255855*102194)^2
93204505789=37*37*41*41*101*401=45510^2+301883^2=1 40958^2+270805^2=283515^2+113242^2=84542^2+293355^ 2 and (45510*301883)^2+(140958*270805)^2=(283515*113242) ^2+(84542*293355)^2
155747446021=37*37*53*53*101*401=58830^2+390239^2= 182214^2+350065^2=109286^2+379215^2=366495^2+14638 6^2 and (58830*390239)^2+(182214*350065)^2=(109286*379215) ^2+(366495*146386)^2
331364408821=37*37*53*73*73*857=549561^2+171310^2= 521330^2+244089^2=313686^2+482665^2=569911^2+81030 ^2 and (549561*171310)^2+(521330*244089)^2=(313686*482665 )^2+(569911*81030)^2
206314078549=37*37*61*61*101*401=67710^2+449143^2= 209718^2+402905^2=421815^2+168482^2=125782^2+43645 5^2 and (67710*449143)^2+(209718*402905)^2=(421815*168482) ^2+(125782*436455)^2
295471035901=37*37*73*73*101*401=81030^2+537499^2= 250974^2+482165^2=504795^2+201626^2=150526^2+52231 5^2 and (81030*537499)^2+(250974*482165)^2=(504795*201626) ^2+(150526*522315)^2
565603309669=37*37*101*101*101*401=112110^2+743663 ^2=347238^2+667105^2=208262^2+722655^2=698415^2+27 8962^2 and (112110*743663)^2+(347238*667105)^2=(208262*722655 )^2+(698415*278962)^2
658752369589=37*37*101*109*109*401=120990^2+802567 ^2=374742^2+719945^2=224758^2+779895^2=753735^2+30 1058^2 and (120990*802567)^2+(374742*719945)^2=(224758*779895 )^2+(753735*301058)^2
707988301261=37*37*101*113*113*401=125430^2+832019 ^2=388494^2+746365^2=233006^2+808515^2=781395^2+31 2106^2 and (125430*832019)^2+(388494*746365)^2=(233006*808515 )^2+(781395*312106)^2
1230953737669=37*37*101*149*149*401=165390^2+10970 87^2=512262^2+984145^2=307238^2+1066095^2=1030335^ 2+411538^2 and (165390*1097087)^2+(512262*984145)^2=(307238*10660 95)^2+(1030335*411538)^2
1366685224981=37*37*101*157*157*401=174270^2+11559 91^2=539766^2+1036985^2=323734^2+1123335^2=1085655 ^2+433634^2 and (174270*1155991)^2+(539766*1036985)^2=(323734*1123 335)^2+(1085655*433634)^2
4378061262109=37*37*101*281*281*401=311910^2+20690 03^2=966078^2+1856005^2=579422^2+2010555^2=1943115 ^2+776122^2 and (311910*2069003)^2+(966078*1856005)^2=(579422*2010 555)^2+(1943115*776122)^2
8915751181069=37*37*101*401*401*401=445110^2+29525 63^2=1378638^2+2648605^2=826862^2+2869155^2=277291 5^2+1107562^2 and (445110*2952563)^2+(1378638*2648605)^2=(826862*286 9155)^2+(2772915*1107562)^2
9827281267429=37*37*101*401*421*421=3099823^2+4673 10^2=2780705^2+1447398^2=3012255^2+868102^2=291121 5^2+1162802^2 and (3099823*467310)^2+(2780705*1447398)^2=(3012255*86 8102)^2+(2911215*1162802)^2
40722163041181=37*37*101*401*857*857=951270^2+6310 091^2=2946366^2+5660485^2=1767134^2+6131835^2=5926 155^2+2367034^2 and (951270*6310091)^2+(2946366*5660485)^2=(1767134*61 31835)^2+(5926155*2367034)^2
406883543629=41*41*53*73*73*857=608973^2+189830^2= 577690^2+270477^2=347598^2+534845^2=631523^2+89790 ^2 and (608973*189830)^2+(577690*270477)^2=(347598*534845 )^2+(631523*89790)^2
679914261781=53*53*53*73*73*857=787209^2+245390^2= 746770^2+349641^2=449334^2+691385^2=816359^2+11607 0^2 and (787209*245390)^2+(746770*349641)^2=(449334*691385 )^2+(816359*116070)^2
900662501989=53*61*61*73*73*857=939583^2+133590^2= 517158^2+795745^2=859490^2+402417^2=906033^2+28243 0^2 and (939583*133590)^2+(517158*795745)^2=(859490*402417 )^2+(906033*282430)^2
1289876504461=53*73*73*73*73*857=1084269^2+337990^ 2=1028570^2+481581^2=618894^2+952285^2=1124419^2+1 59870^2 and (1084269*337990)^2+(1028570*481581)^2=(618894*9522 85)^2+(1124419*159870)^2
2469136840309=53*73*73*101*101*857=1500153^2+46763 0^2=1423090^2+666297^2=856278^2+1317545^2=1555703^ 2+221190^2 and (1500153*467630)^2+(1423090*666297)^2=(856278*1317 545)^2+(1555703*221190)^2
2875778335429=53*73*73*109*109*857=1618977^2+50467 0^2=1535810^2+719073^2=924102^2+1421905^2=1678927^ 2+238710^2 and (1618977*504670)^2+(1535810*719073)^2=(924102*1421 905)^2+(1678927*238710)^2
3090717411421=53*73*73*113*113*857=958014^2+147408 5^2=1740539^2+247470^2=1678389^2+523190^2=1592170^ 2+745461^2 and (958014*1474085)^2+(1740539*247470)^2=(1678389*523 190)^2+(1592170*745461)^2
5373718948309=53*73*73*149*149*857=1263222^2+19437 05^2=2295047^2+326310^2=2213097^2+689870^2=2099410 ^2+982953^2 and (1263222*1943705)^2+(2295047*326310)^2=(2213097*68 9870)^2+(2099410*982953)^2
5966253698341=53*73*73*157*157*857=1331046^2+20480 65^2=2418271^2+343830^2=2331921^2+726910^2=2212130 ^2+1035729^2 and (1331046*2048065)^2+(2418271*343830)^2=(2331921*72 6910)^2+(2212130*1035729)^2
19112392319149=53*73*73*281*281*857=4173693^2+1301 030^2=3959290^2+1853757^2=2382318^2+3665645^2=4328 243^2+615390^2 and (4173693*1301030)^2+(3959290*1853757)^2=(2382318*3 665645)^2+(4328243*615390)^2
38921642295709=53*73*73*401*401*857=5956053^2+1856 630^2=5650090^2+2645397^2=3399678^2+5231045^2=6176 603^2+878190^2 and (5956053*1856630)^2+(5650090*2645397)^2=(3399678*5 231045)^2+(6176603*878190)^2
42900919783669=53*73*73*421*421*857=3569238^2+5491 945^2=6484663^2+921990^2=6253113^2+1949230^2=59318 90^2+2777337^2 and (3569238*5491945)^2+(6484663*921990)^2=(6253113*19 49230)^2+(5931890*2777337)^2
177772285386541=53*73*73*857*857*857=12729021^2+39 67910^2=12075130^2+5653629^2=7265646^2+11179565^2= 13200371^2+1876830^2 and (12729021*3967910)^2+(12075130*5653629)^2=(7265646 *11179565)^2+(13200371*1876830)^2

3. Some of these look to have common factors. For example the one with hypotenuse 1685125 is just what you get by multiplying the generators of the first solution by 5, and in the last solution you found I think all the terms are divisible by 857.
It would be worth filtering these out I think, so we can see if you have come up with any genuinely new ones . My program hasn't found any new ones since the one I last posted, even though I set a faster version of it going moving down from the end of my search space. But congratulations if you have found a better way of discovering solutions than by trial search. I was thinking about trying a program that used the strategy of multiplying to k=3 solutions, but haven't got round to it yet.

4. ## My Search Algorithm

1. Start with a list of 4k+1 primes, including 1. I used ${1,5,13,17,29,37,41,53,61,73,101,109,113,149,157,2 81,401,421,857}$ simply based on the previous data. A bigger list means more solutions. A smaller list means faster results.

2. Calculate all possible combinations of 6 factors. (The eight solutions posed so far have 4 and 5, and I wanted more than eight solutions.) By keeping p=1 a prime, I am guaranteed to consider 0,1,2,3,4,5-factor solutions as well.

3. For each prime, find the corresponding sum of squares. Ex: $5=1^1+2^2$, $13=2^2+3^2$, $17=1^2+4^2$. The literature says such a sum exists, and I'm pretty sure it's unique.

4. (Complicated to code.) For each number N, use the sums of squares of its prime factors to find sums of squares that equal N. Use the identity: $(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(bc-ad)^2=(ad+bc)^2+(bd-ac)^2$. Ex: $13*17=(2^2+3^2)(1^2+4^2)=10^2+11^2=5^2+14^2$. Given N with k factors, this gives you $2^{k-1}$ sums of squares, not necessarily unique.

5. Out of each $(m,n)$ solution to $N=m^2+n^2$, test every possible combination of four unique ones for our second condition: $(m_1n_1)^2+(m_2n_2)^2=(m_3n_3)^2+(m_4n_4)^2$. If it passes, it is a solution!

Some parts of this were difficult to code, but the concept is simple enough. Pro: no factoring, extremely fast and returns lots of solutions. Con: list is NEVER complete, by construction. All values of $a_1$ are necessarily the product of 6 or fewer primes from the initial list. This kind of defeats the purpose of finding random solutions and extracting a pattern. Instead, I am taking a pattern and finding all solutions that exhibit that same pattern.

Attached is the text to the java app I made. There are three possible solutions that this algorithm cannot get: 1) $a_1$ values with more than six prime factors. 2) $a_1$ values with prime factors of the form $4k+3$, but to an even power, so that it is still expressible as the sums of squares. 3) $a_1$ values with prime factors not included in the initial list. There are things we can do to get around these limits, but with a great sacrifice of speed.

I think it's time we shift our attention away from the computing aspect of the problem and go back to the theory: Is there a formula producing these $a_1$ values for which our conditions necessarily hold?

5. Originally Posted by alunw
Some of these look to have common factors. For example the one with hypotenuse 1685125 is just what you get by multiplying the generators of the first solution by 5, and in the last solution you found I think all the terms are divisible by 857.
It would be worth filtering these out I think, so we can see if you have come up with any genuinely new ones . My program hasn't found any new ones since the one I last posted, even though I set a faster version of it going moving down from the end of my search space. But congratulations if you have found a better way of discovering solutions than by trial search. I was thinking about trying a program that used the strategy of multiplying to k=3 solutions, but haven't got round to it yet.
Generally speaking, if two hypotenuses $a_1$ and $a_{11}$ are such that $a_{11} = q^2a_1$ then they belong to the same family. This is the case with $67405$ and $1685125$ since $1685125 = (5^2)(67405)$

6. Originally Posted by Media_Man
I think it's time we shift our attention away from the computing aspect of the problem and go back to the theory: Is there a formula producing these $a_1$ values for which our conditions necessarily hold?
Your conditon 5) is new to me I think. It may make things easier.

I'm currently working off of my mini Ubuntu so the algorithms you guys have will run slow on my laptop.

I suspect the kind of formula your thinking of is currently unknown. For the k = 4 case, I assume that for given inputs $(a,b,c,d,e,f,g,h)$, your looking for some kind of formula $f_n(a,b,c,d,e,f,g,h)$ that outputs the nth k = 4 member, yes?

7. ## A Magic Formula

Originally Posted by jamix
I suspect the kind of formula your thinking of is currently unknown. For the k = 4 case, I assume that for given inputs $(a,b,c,d,e,f,g,h)$, your looking for some kind of formula $f_n(a,b,c,d,e,f,g,h)$ that outputs the nth k = 4 member, yes?
That is correct. If we could find a function $A_n(a,b,c,d,e,f,g,h)$ for the nth k=4 member, then deriving $B_n(a,b,c,d,e,f,g,h)$, $C_n(a,b,c,d,e,f,g,h)$, $E_n(a,b,c,d,e,f,g,h)$ should be straightforward. To get a k=5 member, all we need is two k=4 members such that $A_i=A_j$, $B_i=B_j$, $C_i=C_j$ (multiplying them together guarantees a k=5 member). If we have a formula I am sure we could a) find two k=4 members satisfying these criteria or b) prove none exists.

There is certainly no known formula, otherwise Pomerance would have long since done this.

8. Originally Posted by Media_Man
1. Start with a list of 4k+1 primes, including 1. I used [tex]
3. For each prime, find the corresponding sum of squares. Ex: $5=1^1+2^2$, $13=2^2+3^2$, $17=1^2+4^2$. The literature says such a sum exists, and I'm pretty sure it's unique.
I thought it was known that this was unique, and even that this could be used as a primality test for numbers of this form, but I'm not so sure now as I can't find a reference for this.

9. ## Raw Data

Alunw - I am pretty sure you are correct, though I could not find reference to this fact either. In our specific problem, it makes no difference.

Attached is the updated *.xls file. (Sorry, non-Office users - blame the site, not me.)

At last here is our generating algorithm in simplest form:

$a^2+b^2=c^2+d^2=e^2+f^2=g^2+h^2=A$
$2(a^2b^2+c^2d^2)=2(e^2f^2+g^2h^2)=B$
$2|a^2b^2-c^2d^2|=C_1$
$2|e^2f^2-g^2h^2|=C_2$
(These are the C-values for the two k=3 ladders that multiply to get the desired k=4 ladder)
$\frac12(C_1^2+C_2^2)=C$
$\frac12|C_1^2-C_2^2|=D$

The eight roots can be gotten by $r=a\pm b, c\pm d, e\pm f, g\pm h$ or by $r^2=A\pm\sqrt{B\pm\sqrt{C\pm D}}$

10. I haven't been able to download your last few attachments. I guess its fine (just means I won't be able to add any corrections or whatnot).

Your generating algorithm isn't what I thought you originally had in mind. These conditions can actually be found in a 1999 paper by Dilcher (surprisingly Dilcher's paper is flawed since he claims to have proved that no such integer set $(a,b,,c,d,e,f,g,h)$ can satisfy these conditions ).

To be clear, I don't actually know whether or not there are any k = 5 ladders that have been discovered. I doubt that there has been though. Pomerance probably wouldn't know for sure either. This problem was actually brought up by his coauthor Richard Crandall.

11. ## Pomerance's Text

Jamix - This is from pg 316 in the Crandall/Pomerance textbook:

Theoretical work on such issues does exist; for example, [Dilcher 1999]
discourses on the difficulty of creating longer squaring ladders of the indicated
kind. Recently, D. Symes has discovered a (k = 4) identity, with coefficients
(a1, a2, a3, a4) as implied in the construct
$(((x^2-67405)^2-3525798096)^2-533470702551552000)^2-4692082091913216002$
which, as the reader may wish to verify via symbolic processing, is indeed
the product of 16 monomials! P. Carmody recently reports that many such
4-squarings cases are easy to generate via, say, a GP/Pari script.
Notice that Symes has found our smallest example. So we are pretty far ahead of the curve. I'd be interested in seeing Carmody's results. It says here that Dilcher said the problem was difficult, not impossible. Can you post his paper with the purported faulty proof?

P.S. A few months back when we were working on Carmichael numbers, I was a bit discouraged to have rediscovered something that appeared in a 1910 paper! I feel better now having produced results that are at least as recent as 2005

12. Can you PM me your email address and I'll try sending it to you through my gmail account. I actually tried attaching it a few days ago in the other thread but it wouldn't upload for some reason.

I haven't looked if Carmody has ever published any of his results. Sometimes these guys just like to communicate or muse between each other on what they've got (kinda like we often do on this forum). As k = 4 ladders are still too small to be of any real use as a factoring algorithm, some authors might not publish new ones. On the other hand, you can always try and start a trend. After all, there are all kinds of lists of certain mathematical things or integers that have been documented. For example, Richard Pinch appears to have made it his goal to document every single Carmichael integer he can find.

13. ## Repeats

Good call on the common factors. Turns out, a lot of my solutions were repeats. . My eighty solutions actually only contain eight "primitive" solutions:

67405=1*1*5*13*17*61=227^2+126^2=218^2+141^2=189^2 +178^2=237^2+106^2 and (227*126)^2+(218*141)^2=(189*178)^2+(237*106)^2
600445=1*1*5*29*41*101=613^2+474^2=773^2+54^2=683^ 2+366^2=206^2+747^2 and (613*474)^2+(773*54)^2=(683*366)^2+(206*747)^2
55445869=1*1*37*37*101*401=1110^2+7363^2=3438^2+66 05^2=2062^2+7155^2=6915^2+2762^2 and (1110*7363)^2+(3438*6605)^2=(2062*7155)^2+(6915*27 62)^2
242048509=1*1*53*73*73*857=14853^2+4630^2=14090^2+ 6597^2=8478^2+13045^2=15403^2+2190^2 and (14853*4630)^2+(14090*6597)^2=(8478*13045)^2+(1540 3*2190)^2
5915065=1*5*13*17*53*101=2076^2+1267^2=2428^2+141^ 2=2324^2+717^2=2253^2+916^2 and (2076*1267)^2+(2428*141)^2=(2324*717)^2+(2253*916) ^2
81524605=1*5*17*41*149*157=8498^2+3051^2=8629^2+26 58^2=7947^2+4286^2=9003^2+686^2 and (8498*3051)^2+(8629*2658)^2=(7947*4286)^2+(9003*68 6)^2
532946005=1*5*17*53*281*421=19598^2+12201^2=20583^ 2+10454^2=21366^2+8743^2=17769^2+14738^2 and (19598*12201)^2+(20583*10454)^2=(21366*8743)^2+(17 769*14738)^2
166045477=1*13*17*61*109*113=12606^2+2671^2=10609^ 2+7314^2=12351^2+3674^2=11199^2+6374^2 and (12606*2671)^2+(10609*7314)^2=(12351*3674)^2+(1119 9*6374)^2

Looking at the algebra, it is clear that you can multiply any value of A by a square to get a new solution $x^2A=(xa)^2+(xb)^2...$, like jamix said all along.

Something odd/useful though: Using the same exact algorithm to look for solutions for A up to six factors, these are the only solutions I found, the same eight five-factor ones that you guys found before I made my own algorithm. This means that no combination of six prime factors from the list {1,5,13,17,29,37,41,53,61,73,101,109,113,149,157,2 81,401,421,857} make a solution. All the six-factor solutions I thought I'd found earlier were simply four-factor primitives with an extra $x^2$ factor. I doubt this means no six-factor primitive solutions exist, but I am now intrigued. I'm going to try to run my algorithm with all primes up to 1000, instead of just this small set. Maybe it will terminate in a few *days* and give me what I'm looking for, a six-factor primitive solution.

14. AHA!

12781559905=5*17*29*37*353*397=101256^2+50287^2=39 753^2+105836^2=111992^2+15471^2=76983^2+82796^2 and (101256*50287)^2+(39753*105836)^2=(111992*15471)^2 +(76983*82796)^2

Program still running, but I needed to vindicate myself after that false alarm I pulled.

15. ## Polar fun

Since I'm on a polar binge, I figured a way to run the algorithm a bit smoother using trig. Consider the identity $(a^2+b^2)(c^2+d^2)=(ac\pm bd)^2+(bc\mp ad)^2$. In polar, this is actually $r_1r_2=\left(\sqrt{r_1r_2}\cos(\theta_1\pm\theta_2 )\right)^2+\left(\sqrt{r_1r_2}\sin(\theta_1\pm\the ta_2)\right)^2$

Example: Let $r_1=13=2^2+3^2$ and $r_2=17=1^2+4^2$. Then $\theta_1\approx .9827$ and $\theta_2\approx 1.3258$. And voila...

$\sqrt{221}\cos(.9827+1.3258)=-10$
$\sqrt{221}\sin(.9827+1.3258)=11$
$\sqrt{221}\cos(.9827-1.3258)=14$
$\sqrt{221}\sin(.9827-1.3258)=-5$

So $10^2+11^2=14^2+5^2=221$. So given the factors of a large number N, I can extremely quickly find all integer solutions x,y to $N=x^2+y^2$. For our purposes, we'll need to use a polynomial to approximate sine and cosine for speed, though. This will be much faster than the loop structure and function calls I have in place now.

(After three days, my program is still running, though not turning up anything new . I am trying to pare it down as much as possible for another run.)

Page 2 of 3 First 123 Last