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

Home > Numbers
Recursive reaches one million (Posted on 2019-08-15) Difficulty: 4 of 5
Define a function f mapping positive integers to positive integers by f(1)=1, and f(n)=f(n-1)+n if f(n-1)<=n and f(n)=f(n-1)-n if f(n-1)>n

For n≥2,
i) Find the smallest integer n such that f(n) = 1,000,000
ii) Find the smallest integer n such that f(n) = 2,000,000

No Solution Yet Submitted by Danish Ahmed Khan    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer solution with pattern | Comment 2 of 4 |
There's an obvious pattern within the odd and even numbers taken separately. The odd numbers, starting with 3, go up by 1 until a peak of 8 is reached at n=7; f for even n, starting at 8, increases from 16 to a peak of 23 when n=22 and then diminish to 1 at n=66.

Meanwhile at n=23, the odd values start at 46 (twice 23) and reach a peak of 68 at n=67 (1 higher than where the evens reached 1). The evens start their next climb starting at 136 at n=68 (notice f(68)=2*68). They reach a peak of 203 at n=202, just as the odds, at n=201, have descended down to 1.

The odds resume f values at n=203 with 406 (twice f(202)). Similar patterns seem to repeat after that.

Rather than analyze this pattern to come up with the answers, iteration was carried out far enough to get to the values asked for: the lowest n for f=1,000,000 is 671,396, and the lowest n for f=2,000,000 is 7,957,423.

Contrary to what would be expected from the patterns, 2 million is first reached on a downward trend from more than 2 million. But the again, f values of 24 through 45 were also reached first on a downward trend of odd n's.

The program (iterative programmatically, though recursive mathematically) is:

 f = 1
 For n = 2 To 10000000
   If f <= n Then f = f + n Else f = f - n
   If n <= 2000 Or f >= 1000000 And f <= 1000009 Or f >= 2000000 And f <= 2000100 Then
      Text1.Text = Text1.Text & mform(n, "#########") & mform(f, "##########")
      If n Mod 2 = 0 Or n >= 600000 Then Text1.Text = Text1.Text & crlf
   End If
   DoEvents
 Next


                           2         3
        3         6        4         2
        5         7        6         1
        7         8        8        16
        9         7       10        17
       11         6       12        18
       13         5       14        19
       15         4       16        20
       17         3       18        21
       19         2       20        22
       21         1       22        23
       23        46       24        22
       25        47       26        21
       27        48       28        20
       29        49       30        19
       31        50       32        18
       33        51       34        17
       35        52       36        16
       37        53       38        15
       39        54       40        14
       41        55       42        13
       43        56       44        12
       45        57       46        11
       47        58       48        10
       49        59       50         9
       51        60       52         8
       53        61       54         7
       55        62       56         6
       57        63       58         5
       59        64       60         4
       61        65       62         3
       63        66       64         2
       65        67       66         1
       67        68       68       136
       69        67       70       137
       71        66       72       138
       73        65       74       139
       75        64       76       140
       77        63       78       141
       79        62       80       142
       81        61       82       143
       83        60       84       144
       85        59       86       145
       87        58       88       146
       89        57       90       147
       91        56       92       148
       93        55       94       149
       95        54       96       150
       97        53       98       151
       99        52      100       152
      101        51      102       153
      103        50      104       154
      105        49      106       155
      107        48      108       156
      109        47      110       157
      111        46      112       158
      113        45      114       159
      115        44      116       160
      117        43      118       161
      119        42      120       162
      121        41      122       163
      123        40      124       164
      125        39      126       165
      127        38      128       166
      129        37      130       167
      131        36      132       168
      133        35      134       169
      135        34      136       170
      137        33      138       171
      139        32      140       172
      141        31      142       173
      143        30      144       174
      145        29      146       175
      147        28      148       176
      149        27      150       177
      151        26      152       178
      153        25      154       179
      155        24      156       180
      157        23      158       181
      159        22      160       182
      161        21      162       183
      163        20      164       184
      165        19      166       185
      167        18      168       186
      169        17      170       187
      171        16      172       188
      173        15      174       189
      175        14      176       190
      177        13      178       191
      179        12      180       192
      181        11      182       193
      183        10      184       194
      185         9      186       195
      187         8      188       196
      189         7      190       197
      191         6      192       198
      193         5      194       199
      195         4      196       200
      197         3      198       201
      199         2      200       202
      201         1      202       203
      203       406      204       202
      205       407      206       201
      207       408      208       200
      209       409      210       199
      211       410      212       198
      213       411      214       197
      215       412      216       196
      217       413      218       195
      219       414      220       194
      221       415      222       193
      223       416      224       192
      225       417      226       191
      227       418      228       190
      229       419      230       189
      231       420      232       188
      233       421      234       187
      235       422      236       186
      237       423      238       185
      239       424      240       184
      241       425      242       183
      243       426      244       182
      245       427      246       181
      247       428      248       180
      249       429      250       179
      251       430      252       178
      253       431      254       177
      255       432      256       176
      257       433      258       175
      259       434      260       174
      261       435      262       173
      263       436      264       172
      265       437      266       171
      267       438      268       170
      269       439      270       169
      271       440      272       168
      273       441      274       167
      275       442      276       166
      277       443      278       165
      279       444      280       164
      281       445      282       163
      283       446      284       162
      285       447      286       161
      287       448      288       160
      289       449      290       159
      291       450      292       158
      293       451      294       157
      295       452      296       156
      297       453      298       155
      299       454      300       154
      301       455      302       153
      303       456      304       152
      305       457      306       151
      307       458      308       150
      309       459      310       149
      311       460      312       148
      313       461      314       147
      315       462      316       146
      317       463      318       145
      319       464      320       144
      321       465      322       143
      323       466      324       142
      325       467      326       141
      327       468      328       140
      329       469      330       139
      331       470      332       138
      333       471      334       137
      335       472      336       136
      337       473      338       135
      339       474      340       134
      341       475      342       133
      343       476      344       132
      345       477      346       131
      347       478      348       130
      349       479      350       129
      351       480      352       128
      353       481      354       127
      355       482      356       126
      357       483      358       125
      359       484      360       124
      361       485      362       123
      363       486      364       122
      365       487      366       121
      367       488      368       120
      369       489      370       119
      371       490      372       118
      373       491      374       117
      375       492      376       116
      377       493      378       115
      379       494      380       114
      381       495      382       113
      383       496      384       112
      385       497      386       111
      387       498      388       110
      389       499      390       109
      391       500      392       108
      393       501      394       107
      395       502      396       106
      397       503      398       105
      399       504      400       104
      401       505      402       103
      403       506      404       102
      405       507      406       101
      407       508      408       100
      409       509      410        99
      411       510      412        98
      413       511      414        97
      415       512      416        96
      417       513      418        95
      419       514      420        94
      421       515      422        93
      423       516      424        92
      425       517      426        91
      427       518      428        90
      429       519      430        89
      431       520      432        88
      433       521      434        87
      435       522      436        86
      437       523      438        85
      439       524      440        84
      441       525      442        83
      443       526      444        82
      445       527      446        81
      447       528      448        80
      449       529      450        79
      451       530      452        78
      453       531      454        77
      455       532      456        76
      457       533      458        75
      459       534      460        74
      461       535      462        73
      463       536      464        72
      465       537      466        71
      467       538      468        70
      469       539      470        69
      471       540      472        68
      473       541      474        67
      475       542      476        66
      477       543      478        65
      479       544      480        64
      481       545      482        63
      483       546      484        62
      485       547      486        61
      487       548      488        60
      489       549      490        59
      491       550      492        58
      493       551      494        57
      495       552      496        56
      497       553      498        55
      499       554      500        54
      501       555      502        53
      503       556      504        52
      505       557      506        51
      507       558      508        50
      509       559      510        49
      511       560      512        48
      513       561      514        47
      515       562      516        46
      517       563      518        45
      519       564      520        44
      521       565      522        43
      523       566      524        42
      525       567      526        41
      527       568      528        40
      529       569      530        39
      531       570      532        38
      533       571      534        37
      535       572      536        36
      537       573      538        35
      539       574      540        34
      541       575      542        33
      543       576      544        32
      545       577      546        31
      547       578      548        30
      549       579      550        29
      551       580      552        28
      553       581      554        27
      555       582      556        26
      557       583      558        25
      559       584      560        24
      561       585      562        23
      563       586      564        22
      565       587      566        21
      567       588      568        20
      569       589      570        19
      571       590      572        18
      573       591      574        17
      575       592      576        16
      577       593      578        15
      579       594      580        14
      581       595      582        13
      583       596      584        12
      585       597      586        11
      587       598      588        10
      589       599      590         9
      591       600      592         8
      593       601      594         7
      595       602      596         6
      597       603      598         5
      599       604      600         4
      601       605      602         3
      603       606      604         2
      605       607      606         1
      607       608      608      1216
      609       607      610      1217
      611       606      612      1218
      613       605      614      1219
      615       604      616      1220
      617       603      618      1221
      619       602      620      1222
      621       601      622      1223
      623       600      624      1224
      625       599      626      1225
      627       598      628      1226
      629       597      630      1227
      631       596      632      1228
      633       595      634      1229
      635       594      636      1230
      637       593      638      1231
      639       592      640      1232
      641       591      642      1233
      643       590      644      1234
      645       589      646      1235
      647       588      648      1236
      649       587      650      1237
      651       586      652      1238
      653       585      654      1239
      655       584      656      1240
      657       583      658      1241
      659       582      660      1242
      661       581      662      1243
      663       580      664      1244
      665       579      666      1245
      667       578      668      1246
      669       577      670      1247
      671       576      672      1248
      673       575      674      1249
      675       574      676      1250
      677       573      678      1251
      679       572      680      1252
      681       571      682      1253
      683       570      684      1254
      685       569      686      1255
      687       568      688      1256
      689       567      690      1257
      691       566      692      1258
      693       565      694      1259
      695       564      696      1260
      697       563      698      1261
      699       562      700      1262
      701       561      702      1263
      703       560      704      1264
      705       559      706      1265
      707       558      708      1266
      709       557      710      1267
      711       556      712      1268
      713       555      714      1269
      715       554      716      1270
      717       553      718      1271
      719       552      720      1272
      721       551      722      1273
      723       550      724      1274
      725       549      726      1275
      727       548      728      1276
      729       547      730      1277
      731       546      732      1278
      733       545      734      1279
      735       544      736      1280
      737       543      738      1281
      739       542      740      1282
      741       541      742      1283
      743       540      744      1284
      745       539      746      1285
      747       538      748      1286
      749       537      750      1287
      751       536      752      1288
      753       535      754      1289
      755       534      756      1290
      757       533      758      1291
      759       532      760      1292
      761       531      762      1293
      763       530      764      1294
      765       529      766      1295
      767       528      768      1296
      769       527      770      1297
      771       526      772      1298
      773       525      774      1299
      775       524      776      1300
      777       523      778      1301
      779       522      780      1302
      781       521      782      1303
      783       520      784      1304
      785       519      786      1305
      787       518      788      1306
      789       517      790      1307
      791       516      792      1308
      793       515      794      1309
      795       514      796      1310
      797       513      798      1311
      799       512      800      1312
      801       511      802      1313
      803       510      804      1314
      805       509      806      1315
      807       508      808      1316
      809       507      810      1317
      811       506      812      1318
      813       505      814      1319
      815       504      816      1320
      817       503      818      1321
      819       502      820      1322
      821       501      822      1323
      823       500      824      1324
      825       499      826      1325
      827       498      828      1326
      829       497      830      1327
      831       496      832      1328
      833       495      834      1329
      835       494      836      1330
      837       493      838      1331
      839       492      840      1332
      841       491      842      1333
      843       490      844      1334
      845       489      846      1335
      847       488      848      1336
      849       487      850      1337
      851       486      852      1338
      853       485      854      1339
      855       484      856      1340
      857       483      858      1341
      859       482      860      1342
      861       481      862      1343
      863       480      864      1344
      865       479      866      1345
      867       478      868      1346
      869       477      870      1347
      871       476      872      1348
      873       475      874      1349
      875       474      876      1350
      877       473      878      1351
      879       472      880      1352
      881       471      882      1353
      883       470      884      1354
      885       469      886      1355
      887       468      888      1356
      889       467      890      1357
      891       466      892      1358
      893       465      894      1359
      895       464      896      1360
      897       463      898      1361
      899       462      900      1362
      901       461      902      1363
      903       460      904      1364
      905       459      906      1365
      907       458      908      1366
      909       457      910      1367
      911       456      912      1368
      913       455      914      1369
      915       454      916      1370
      917       453      918      1371
      919       452      920      1372
      921       451      922      1373
      923       450      924      1374
      925       449      926      1375
      927       448      928      1376
      929       447      930      1377
      931       446      932      1378
      933       445      934      1379
      935       444      936      1380
      937       443      938      1381
      939       442      940      1382
      941       441      942      1383
      943       440      944      1384
      945       439      946      1385
      947       438      948      1386
      949       437      950      1387
      951       436      952      1388
      953       435      954      1389
      955       434      956      1390
      957       433      958      1391
      959       432      960      1392
      961       431      962      1393
      963       430      964      1394
      965       429      966      1395
      967       428      968      1396
      969       427      970      1397
      971       426      972      1398
      973       425      974      1399
      975       424      976      1400
      977       423      978      1401
      979       422      980      1402
      981       421      982      1403
      983       420      984      1404
      985       419      986      1405
      987       418      988      1406
      989       417      990      1407
      991       416      992      1408
      993       415      994      1409
      995       414      996      1410
      997       413      998      1411
      999       412     1000      1412
     1001       411     1002      1413
     1003       410     1004      1414
     1005       409     1006      1415
     1007       408     1008      1416
     1009       407     1010      1417
     1011       406     1012      1418
     1013       405     1014      1419
     1015       404     1016      1420
     1017       403     1018      1421
     1019       402     1020      1422
     1021       401     1022      1423
     1023       400     1024      1424
     1025       399     1026      1425
     1027       398     1028      1426
     1029       397     1030      1427
     1031       396     1032      1428
     1033       395     1034      1429
     1035       394     1036      1430
     1037       393     1038      1431
     1039       392     1040      1432
     1041       391     1042      1433
     1043       390     1044      1434
     1045       389     1046      1435
     1047       388     1048      1436
     1049       387     1050      1437
     1051       386     1052      1438
     1053       385     1054      1439
     1055       384     1056      1440
     1057       383     1058      1441
     1059       382     1060      1442
     1061       381     1062      1443
     1063       380     1064      1444
     1065       379     1066      1445
     1067       378     1068      1446
     1069       377     1070      1447
     1071       376     1072      1448
  Posted by Charlie on 2019-08-15 09:18: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 (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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