All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Define the members of S (Posted on 2024-02-18) Difficulty: 3 of 5
Let S be the smallest set of positive integers such that
a) 2 is in S,
b) n is in S whenever n^2 is in S, and
c) (n + 5)^2 is in S whenever n is in S.
Which positive integers are not in S?

(The set S is “smallest” in the sense that S is contained in any other such set.)

Source: Putnam 2017

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts flawed program, but some ideas | Comment 1 of 3
clearvars,clc
S=2;
i=1;
while i<=599
  n=S(i);
  if n<1000000
    S(end+1)=(n+5)^2;
    sr=round(sqrt(n));
    if sr^2==n
      S(end+1)=sr;
      S=unique(S,'stable');
      i=find(S==sr);
    else
      i=i+1;
    end
  else
    i=i+1;
  end
end
S=unique(S);
fprintf('%4d, %4d, %4d, %4d, %4d, %4d, %4d, %4d, %4d, ',S)


   2,    7,   12,   17,   22,   27,   32,   37,   42, 
  47,   49,   52,   57,   62,   67,   72,   77,   82, 
  87,   92,   97,  102,  107,  112,  117,  122,  127, 
 132,  137,  142,  144,  147,  152,  157,  162,  167, 
 172,  177,  182,  187,  192,  197,  202,  207,  212, 
 217,  222,  227,  232,  237,  242,  247,  252,  257, 
 262,  267,  272,  277,  282,  287,  289,  292,  297, 
 302,  307,  312,  317,  322,  327,  332,  337,  342, 
 347,  352,  357,  362,  367,  372,  377,  382,  387, 
 392,  397,  402,  407,  412,  417,  422,  427,  432, 
 437,  442,  447,  452,  457,  462,  467,  472,  477, 
 482,  484,  487,  492,  497,  502,  507,  512,  517, 
 522,  527,  532,  537,  542,  547,  552,  557,  562, 
 567,  572,  577,  582,  587,  592,  597,  602,  607, 
 612,  617,  622,  627,  632,  637,  642,  647,  652, 
 657,  662,  667,  672,  677,  682,  687,  692,  697, 
 702,  707,  712,  717,  722,  727,  729,  732,  737, 
 742,  747,  752,  757,  762,  767,  772,  777,  782, 
 787,  792,  797,  802,  807,  812,  817,  822,  827, 
 832,  837,  842,  847,  852,  857,  862,  867,  872, 
 877,  882,  887,  892,  897,  902,  907,  912,  917, 
 922,  927,  932,  937,  942,  947,  952,  957,  962, 
 967,  972,  977,  982,  987,  992,  997, 1024, 1369, 
1764, 2209, 2704, 2916, 3249, 3844, 4489, 5184, 5929, 
6724, 7569, 8464, 9409, 10404, 11449, 12544, 13689, 14884, 
16129, 17424, 18769, 20164, 21609, 22201, 23104, 24649, 26244, 
27889, 29584, 31329, 33124, 34969, 36864, 38809, 40804, 42849, 
44944, 47089, 49284, 51529, 53824, 56169, 58564, 61009, 63504, 
66049, 68644, 71289, 73984, 76729, 79524, 82369, 85264, 86436, 
88209, 91204, 94249, 97344, 100489, 103684, 106929, 110224, 113569, 
116964, 120409, 123904, 127449, 131044, 134689, 138384, 142129, 145924, 
149769, 153664, 157609, 161604, 165649, 169744, 173889, 178084, 182329, 
186624, 190969, 195364, 199809, 204304, 208849, 213444, 218089, 222784, 
227529, 232324, 237169, 239121, 242064, 247009, 252004, 257049, 262144, 
267289, 272484, 277729, 283024, 288369, 293764, 299209, 304704, 310249, 
315844, 321489, 327184, 332929, 338724, 344569, 350464, 356409, 362404, 
368449, 374544, 380689, 386884, 393129, 399424, 405769, 412164, 418609, 
425104, 431649, 438244, 444889, 451584, 458329, 465124, 471969, 478864, 
485809, 492804, 499849, 506944, 514089, 521284, 528529, 535824, 538756, 
543169, 550564, 558009, 565504, 573049, 580644, 588289, 595984, 603729, 
611524, 619369, 627264, 635209, 643204, 651249, 659344, 667489, 675684, 
683929, 692224, 700569, 708964, 717409, 725904, 734449, 743044, 751689, 
760384, 769129, 777924, 786769, 795664, 804609, 813604, 822649, 831744, 
840889, 850084, 859329, 868624, 877969, 887364, 896809, 906304, 915849, 
925444, 935089, 944784, 954529, 964324, 974169, 984064, 994009, 1004004, 
1058841, 1887876, 3129361, 4901796, 7338681, 10588516, 14814801, 20196036, 26925721, 
35212356, 45279441, 57365476, 71723961, 88623396, 108347281, 131194116, 157477401, 187525636, 
221682321, 260305956, 303770041, 352463076, 406788561, 467164996, 534025881, 607819716, 689010001, 
778075236, 875508921, 981819556, 1097530641, 1223180676, 1359323161, 1506526596, 1665374481, 1836465316, 
2020412601, 2217844836, 2429405521, 2655753156, 2897561241, 3155518276, 3430327761, 3722708196, 4033393081, 
4363130916, 4712685201, 5082834436, 5474372121, 5888106756, 6324861841, 6785475876, 7270802361, 7781709796, 
8319081681, 8883816516, 9476827801, 10099044036, 10751408721, 11434880356, 12150432441, 12899053476, 13681746961, 
14499531396, 15353440281, 16244522116, 17173840401, 18142473636, 19151515321, 20202073956, 21295273041, 22432251076, 
23614161561, 24842172996, 26117468881, 27441247716, 28814723001, 30239123236, 31715691921, 33245687556, 34830383641, 
36471068676, 38169046161, 39925634596, 41742167481, 43619993316, 45560475601, 47564992836, 49634938521, 51771721156, 
53976764241, 56251506276, 58597400761, 61015916196, 63508536081, 66076758916, 68722098201, 71446082436, 74250255121, 
77136174756, 80105414841, 83159563876, 86300225361, 89529017796, 92847574681, 96257544516, 99760590801, 103358392036, 
107052641721, 110845048356, 114737335441, 118731241476, 122828519961, 127030939396, 131340283281, 135758350116, 140286953401, 
144927921636, 149683098321, 154554341956, 159543526041, 164652539076, 169883284561, 175237680996, 180717661881, 186325175716, 
192062186001, 197930671236, 203932624921, 210070055556, 216344986641, 222759456676, 229315519161, 236015242596, 242860710481, 
249854021316, 256997288601, 264292640836, 271742221521, 279348189156, 287112717241, 295037994276, 303126223761, 311379624196, 
319800429081, 328390886916, 337153261201, 346089830436, 355202888121, 364494742756, 373967717841, 383624151876, 393466398361, 
403496825796, 413717817681, 424131772516, 434741103801, 445548240036, 456555624721, 467765716356, 479180988441, 490803929476, 
502637042961, 514682847396, 526943876281, 539422678116, 552121816401, 565043869636, 578191431321, 591567109956, 605173529041, 
619013327076, 633089157561, 647403688996, 661959604881, 676759603716, 691806399001, 707102719236, 722651307921, 738454923556, 
754516339641, 770838344676, 787423742161, 804275350596, 821396003481, 838788549316, 856455851601, 874400788836, 892626254521, 
911135157156, 929930420241, 949014982276, 968391796761, 988063832196, >> 

There's a flaw in the program, that it isn't infinite.

Note that 49 is on the list, but not 54. But 49+5 = 54 so that 54^2 = 2916 is on the list. That means sqrt(2916) = 54 should be on the list, but we never get to examining it due to the limit on i.

But we do see the integers ending in 2 and 7 are apparent on the list, and eventually those ending in 4 and 9 and 1 and 6 appear.

Absent on this list are numbers ending in 3 and 8 and in 0 and 5. Is this significant, or an artifact of the flaw in the program?

Edited on February 18, 2024, 10:23 am
  Posted by Charlie on 2024-02-18 10:22:37

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information