# Square root multiples

This is based on OEIS sequence A261865.

$$\A261865(n)\$$ is the least integer $$\k\$$ such that some multiple of $$\\sqrt{k}\$$ is in the interval $$\(n,n+1)\$$.

The goal of this challenge is to write a program that can find a value of $$\n\$$ that makes $$\A261865(n)\$$ as large as you can. A brute-force program can probably do okay, but there are other methods that you might use to do even better.

### Example

For example, $$\A261865(3) = 3\$$ because

• there is no multiple of $$\\sqrt{1}\$$ in $$\(3,4)\$$ (since $$\3 \sqrt{1} \leq 3\$$ and $$\4 \sqrt{1} \geq 4\$$);
• there is no multiple of $$\\sqrt{2}\$$ in $$\(3,4)\$$ (since $$\2 \sqrt{2} \leq 3\$$ and $$\3 \sqrt{2} \geq 4\$$);
• and there is a multiple of $$\\sqrt{3}\$$ in $$\(3,4)\$$, namely $$\2\sqrt{3} \approx 3.464\$$.

### Analysis

Large values in this sequence are rare!

• 70.7% of the values are $$\2\$$s,
• 16.9% of the values are $$\3\$$s,
• 5.5% of the values are $$\5\$$s,
• 2.8% of the values are $$\6\$$s,
• 1.5% of the values are $$\7\$$s,
• 0.8% of the values are $$\10\$$s, and
• 1.7% of the values are $$\\geq 11\$$.

### Challenge

The goal of this is to write a program that finds a value of $$\n\$$ that makes $$\A261865(n)\$$ as large as possible. Your program should run for no more than one minute and should output a number $$\n\$$. Your score is given by $$\A261865(n)\$$. In the case of a close call, I will run all entries on my 2017 MacBook Pro with 8GB of RAM to determine the winner.

For example, you program might output $$\A261865(257240414)=227\$$ for a score of 227. If two entries get the same score, whichever does it faster on my machine is the winner.

(Your program should not rely on information about pre-computed values, unless you can justify that information with a heuristic or a proof.)

• Uh, should we compute some large value in one minute or the guaranteed maximum of A(1), A(2), …, to some point A(n) within the time limit? – xash Feb 27 at 17:28
• @xash, compute one large value of A(n) within the time limit. – Peter Kagey Feb 27 at 18:31
• It doesn’t have to be a “record” value. (That is, it’s okay if there’s some m<n with A(m)>A(n).) – Peter Kagey Feb 27 at 18:40
• @Sheik, I updated the question to try to address any confusion. I hope this helps! – Peter Kagey Feb 28 at 7:18
• I think that the next best answer is going to have something to do with continued fraction. – user202729 Mar 1 at 9:35

# C++ (clang), score $$\399\$$

#include <iostream>
#include <cmath>
#include <vector>
#include <thread>

void f(unsigned long n)
{
unsigned int m = 0;
while (1) {
unsigned long k = 1;
while (++k) {
const double sqrt_k = std::sqrt(static_cast<double>(k));
const double x = sqrt_k * std::ceil(n/sqrt_k);
if (n < x && x < n + 1) break;
}
if (k > m) {
std::cout << "<" << k << "> for A261865(" << n << ")\n";
m = k;
}
++n;
}
}

int main()
{
const unsigned long block_size = 100000000000UL;
const unsigned long num_threads = 12;
std::vector<unsigned int> results(num_threads);
std::vector<std::thread> threads(num_threads - 1);
unsigned long start = 1UL;
for (int i = 0; i < num_threads - 1; ++i) {
threads[i] = std::thread(f, start);
start += block_size;
}
for (auto& entry: threads) {
entry.join();
}
}


Try it online!

Gets $$\313\$$ on TIO.
Gets $$\399\$$ on my laptop (Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz with 16 GB RAM):

#include <iostream>
#include <cmath>
#include <sys/time.h>
#include <vector>
#include <thread>

int sigTimerSet(int seconds)
{
std::cout << "Starting timer for " << seconds << " seconds.\n";

struct itimerval old_one, new_one;
new_one.it_interval.tv_usec = 0;
new_one.it_interval.tv_sec = 0;
new_one.it_value.tv_usec = 0;
new_one.it_value.tv_sec = static_cast<long int>(seconds);
if (setitimer (ITIMER_REAL, &new_one, &old_one) < 0)
return 0;
else
return old_one.it_value.tv_sec;
}

void f(unsigned long n)
{
unsigned int m = 0;
while (1) {
unsigned long k = 1;
while (++k) {
const double sqrt_k = std::sqrt(static_cast<double>(k));
const double x = sqrt_k * std::ceil(n/sqrt_k);
if (n < x && x < n + 1) break;
}
if (k > m) {
std::cout << "<" << k << "> for A261865(" << n << ")\n";
m = k;
}
++n;
}
}

int main()
{
sigTimerSet(60);

const unsigned long block_size = 100000000000UL;
const unsigned long num_threads = std::thread::hardware_concurrency();
std::vector<unsigned int> results(num_threads);
std::vector<std::thread> threads(num_threads - 1);
unsigned long start = 1UL;
for (int i = 0; i < num_threads - 1; ++i) {
threads[i] = std::thread(f, start);
start += block_size;
}
for (auto& entry: threads) {
entry.join();
}
}


produces:

Starting timer for 60 seconds.
<2> for A261865(1)
<3> for A261865(3)
<7> for A261865(23)
<15> for A261865(30)
<38> for A261865(184)
<3> for A261865(200000000001)
<2> for A261865(300000000001)
<3> for A261865(300000000003)
<<2> for A261865(60000000000143)
<<5> for A261865(3000000000065)
<<6> for A261865(300000000016)
<14> for A261865(300000000023)
<15> for A261865(300000000115)
<19> for A261865(300000000160)
<21> for A261865(300000000399)
<26> for A261865(300000000716)
<2> for A261865(400000000001)
<5> for A261865(400000000002)
<6> for A261865(400000000032)
<11> for A261865(400000000039)
<14> for A261865(400000000063)
<53> for A261865(400000000316)
<3> for A261865(600000000003)
<5> for A261865(600000000006)
<6> for A261865(600000000016)
<295> for A261865(400000002890)
<2> for A261865(900000000001)
<6> for A261865(900000000003)
<10> for A261865(900000000037)
<17> for A261865(900000000108)
<19> for A261865(900000000320)
<30> for A261865(900000000522)
<31> for A261865(900000001146)
<2> for A261865(800000000001)
<5> for A261865(800000000004)
<6> for A261865(800000000034)
<11> for A261865(800000000072)
<<39> for A261865(900000003574)
<35> for A261865(800000000079)
38<<> for A261865(300000002673)
> for A261865(<2> for A261865(100000000001)
<5> for A261865(100000000002)
> for A261865(<13> for A261865(100000000009)
<21> for A261865(100000000340)
<> for A261865(<29> for A261865(100000001644)
77> for A261865(<> for A261865(600000000027)
<10> for A261865(600000000037)
<15> for A261865(600000000068)
<21> for A261865(600000000139)
8091)
51> for A261865(900000008337)
<13> for A261865(1000000000001)
<15> for A261865(1000000000018)
<23> for A261865(1000000000124)
<46> for A261865(16060)
<<29> for A261865(1000000002029)
<38> for A261865(1000000002313)
200000000004)
<10> for A261865(200000000014)
<11> for A261865(200000000028)
<13> for A261865(200000000383)
<17> for A261865(200000000584)
<23> for A261865(200000000861)
71<46> for A261865(200000001329)
42> for A261865(300000003489)
<58> for A261865(200000003435)
<53> for A261865(300000004909)
<<62> for A261865(200000006771)
<30> for A261865(100000003880)
<37> for A261865(100000004041)
> for A261865(<38> for A261865(100000004980)
<<39> for A261865(100000005673)
700000000001)
<51> for A261865(100000008489)
<10> for A261865(700000000063)
<15> for A261865(700000000077)
<19> for A261865(700000000264)
500000000001<26> for A261865(700000001087)
39<30> for A261865(700000001941)
<<38> for A261865(700000002098)
800000005135<43> for A261865(700000002630)
29> for A261865(600000001409)
> for A261865()
<<5> for A261865(500000000004)
31> for A261865(600000003011)
)
1000000003259)
<42> for A261865(1000000005365)
<62> for A261865(300000022786)
<73> for A261865(700000007516)
<35> for A261865(600000003458)
<53> for A261865(1000000014642)
<58> for A261865(16907)
<67> for A261865(600000006910)
<55> for A261865(100000020333)
<79> for A261865(200000057626)
<21> for A261865(500000000018)
<<23> for A261865(500000001052)
<<33> for A261865(500000001414)
<35> for A261865(500000001568)
<<70> for A261865(300000025183)
62> for A261865(100000024519)
61> for A261865(20993)
65> for A261865(1000000025765)
85<74> for A261865(100000027954)
<97> for A261865(26286)
> for A261865(900000026060)
<66> for A261865(1000000037855)
<79> for A261865(100000035523)
<85> for A261865(200000088176)
<93> for A261865(900000037207)
<97> for A261865(300000061052)
<79> for A261865(600000074122)
<78> for A261865(800000098681)
<122> for A261865(400000213561)
<79> for A261865(700000110055)
<101> for A261865(900000115082)
<118> for A261865(130375)
<95> for A261865(600000136687)
<85> for A261865(700000175977)
<127> for A261865(169819)
<74> for A261865(1000000208668)
<95> for A261865(200000283049)
<95> for A261865(100000278291)
<79> for A261865(800000325129)
<83> for A261865(800000382758)
<101> for A261865(300000348034)
<82> for A261865(1000000377945)
<113> for A261865(600000368089)
<115> for A261865(600000388325)
<114> for A261865(900000458149)
<94> for A261865(800000523290)
<57> for A261865(500000002957)
<91> for A261865(500000020356)
<94> for A261865(500000086735)
<123> for A261865(1000000615915)
<139> for A261865(900000597046)
<113> for A261865(700000641956)
<122> for A261865(500000189745)
<138> for A261865(500000344679)
<109> for A261865(300000963142)
<129> for A261865(600001013758)
<139> for A261865(400001233496)
<177> for A261865(300001283249)
<107> for A261865(800001360974)
<110> for A261865(100001440670)
<119> for A261865(200001950373)
<127> for A261865(200002180270)
<119> for A261865(100001936762)
<130> for A261865(2135662)
<123> for A261865(700002323159)
<146> for A261865(600001831667)
<187> for A261865(2345213)
<109> for A261865(800002595588)
<145> for A261865(700002807851)
<155> for A261865(500003070679)
<194> for A261865(300003944386)
<127> for A261865(1000003765582)
<142> for A261865(1000003972101)
<165> for A261865(100003914551)
<110> for A261865(800004935331)
<141> for A261865(200005383478)
<186> for A261865(800005847131)
<157> for A261865(600005644046)
<185> for A261865(200006038768)
<178> for A261865(400008172024)
<183> for A261865(500008457011)
<163> for A261865(1000010164463)
<190> for A261865(800013713435)
<146> for A261865(900015388529)
<197> for A261865(600016805653)
<155> for A261865(700016980104)
<165> for A261865(1000017298685)
<185> for A261865(1000023033133)
<186> for A261865(100022787204)
<157> for A261865(700023653342)
<161> for A261865(700024255285)
<159> for A261865(900023644405)
<202> for A261865(900027523835)
<303> for A261865(700033230641)
<199> for A261865(300035412403)
<215> for A261865(500035617384)
<195> for A261865(800035729684)
<223> for A261865(600037942250)
<193> for A261865(46272966)
<221> for A261865(500060347857)
<197> for A261865(100072149460)
<226> for A261865(200071020948)
<219> for A261865(800096272342)
<273> for A261865(100096408342)
<195> for A261865(1000138255835)
<313> for A261865(600147859274)
<210> for A261865(300158020199)
<305> for A261865(300163012534)
<179> for A261865(400173203199)
<249> for A261865(500185649969)
<281> for A261865(900217000298)
<210> for A261865(222125822)
<222> for A261865(1000221604207)
<217> for A261865(237941698)
<227> for A261865(257240414)
<229> for A261865(1000299563639)
<191> for A261865(400330753112)
<237> for A261865(800371022066)
<197> for A261865(400388377102)
<222> for A261865(400519662337)
<247> for A261865(1000659372263)
<251> for A261865(400686850499)
<293> for A261865(900791054060)
<258> for A261865(201101992489)
<267> for A261865(1205703469)
<255> for A261865(501227521557)
<258> for A261865(501233713968)
<399> for A261865(1001313673399)
<299> for A261865(1558293414)
<271> for A261865(801556690220)
<286> for A261865(501665988151)
<257> for A261865(401963829763)
<357> for A261865(901991228083)
<290> for A261865(101979205483)
<293> for A261865(102084473850)
<282> for A261865(402539565301)
Alarm clock


Note the <399> for A261865(1001313673399)! :D

• 399.....woohoo! – Anush Feb 28 at 14:01

# C (gcc), A261865(6600656102)=323 on TIO

This out this checks every A(n) sequentially (well, based on the small CHUNKSIZE, and it skips a lot of values based on optimization, see the How it works).

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <stdint.h>

//#define L unsigned __int128
//#define F __float128
#define L unsigned long long
#define F long double
#define MAXN (1024ull*1024ull*1024ull*1024ull)
#define CHUNKSIZE (1024ull*1024ull)
#define CHECKS 8
#define BUFFER 1024

int main() {
F steps[CHECKS + BUFFER], values[CHECKS + BUFFER];
steps = sqrtl(2) / (sqrtl(2) - 1);
steps = sqrtl(3) / (sqrtl(3) - 1);
int n=5, min_check;
for (int i = 2; i < CHECKS + BUFFER; n++) {
int ok = 1;
for (int tmp = 2; tmp < sqrtl(n) + 0.5; tmp++)
if (n % (tmp * tmp) == 0) ok = 0;
if (!ok)
continue;
values[i] = n;
steps[i++] = sqrtl(n);
if (i == CHECKS) min_check = i;
}

char chunk[CHUNKSIZE] = { 0 };

#pragma omp parallel for private(chunk) schedule(static, 1)
for (L chunki = 0; chunki < (MAXN / CHUNKSIZE); chunki++) {

L start = chunki * CHUNKSIZE, end = (chunki + 1) * CHUNKSIZE;

for (L i = start / steps + 1; i < end / steps; i++)
chunk[(L)(i * steps) - start] = 1;
for (int k = 2; k < CHECKS; k++)
for (L i = start / steps[k] + 1; i < end / steps[k]; i++)
chunk[(L)(i * steps[k]) - start] = 0;

for (L i = start / steps + 1; i < end / steps; i++) {
L xi = (L)(i * steps) - start;
if (chunk[xi] == 1) {
chunk[xi] = 0;
L x = xi + start;
int k = min_check;
while (++k) {
F sqrt_k = steps[k];
F try = sqrt_k * ceill(x/sqrt_k);
if (x < try && try < x + 1) break;
}
k = values[k];
if (k > 249)
printf("A261865(%llu)=%d\n", x, k), fflush(stdout);
}
}
}
}


Try it online!

### How it works

We sieve through the numbers: floor(i * sqrt(n)) is a Beatty sequence. The nice thing about these is that their complement is easy to calculate. So if floor(i * sqrt(2)) hits 1 2 4 5 7 8 9 …, floor(i * (sqrt(2) / (sqrt(2) - 1))) hits 3 6 10 13 17 20 23 … This alone saves us about two third calculation time.

For n>4, sqrt(n) is actually bigger than (sqrt(2) / (sqrt(2) - 1). So we initialize an array of 0s, set every non-multiple of sqrt(3) to 1, and for every n between 3 and CHECKS we set every multiple of sqrt(n) back to 0. We then take the big steps of (sqrt(2) / (sqrt(2) - 1) and if there the array is set to 1, we know that A(i) is at least CHECKS.

A(n) must be a square free number, as the square of its square divisor (8 -> 4 -> 2) will already have hit the same numbers, so we can skip 4 8 9 12 16 …, too.

The actual computation of A(n) is borrowed from @Noodle9. But we can start with i = CHECKS.

Bundled all of this with OpenMP for easy multithreading for the chunks and some performance testing to get a good value for CHECKS, we get to 383 on TIO. If you want to get further than A(2^64), you need to define L and F to unsigned __int128 and __float128.

• Why would this find A261865(557784208155) = 383 but not A261865(105991039757) = 385 or A261865(119034690206) = 397? – Neil Feb 28 at 17:27
• @Neil Oh, OpenMP reorders the chunks more than I thought, thus the earlier values get skipped. This feels like a magic constant, so I'll drop the multithreading for now. Thanks for noticing! – xash Feb 28 at 17:36
• @Neil Fixed the chunk order to be sequentially. And some rounding errors have also crawled in. But the max value I get in TIO now gets verified by your version with __int128, so that is something I should have done earlier. :-) – xash Feb 28 at 18:03

# JavaScript (Node.js), score $$\335\$$

Pretty straight-forward algorithm. I made it multithreaded to be a bit faster.

// Run with: node ./square-root-multiples.js

const findMaxK = (fromN, toN) => {
let maxK = 0;
let maxN = 0;
for (let n = fromN; n < toN; n++) {
for (let k = 2, s = n * n; k < s; k++) {
const r = Math.sqrt(k);
const x = r * Math.ceil(n / r);
if (x > n && x < n + 1) {
if (k > maxK) {
maxK = k;
maxN = n;
}
break;
}
}
}
return { n: maxN, k: maxK };
};

const BATCH_SIZE = 10000000;

const cluster = require("cluster");
if (cluster.isMaster) {
const start = Date.now();
let nextBatch = 0;
let maxK = 0;

const numCpus = require("os").cpus().length;
for (let i = 0; i < numCpus; i++) {
const worker = cluster.fork();
worker.on("message", (msg) => {
if (msg.k > maxK) {
maxK = msg.k;
console.log(
found A261865(${msg.n}) =${msg.k} in \${
(Date.now() - start) / 1000
}s
);
}
worker.send({ n: nextBatch, maxK });
nextBatch += BATCH_SIZE;
});
worker.send({ n: nextBatch });
nextBatch += BATCH_SIZE;
}
} else {
process.on("message", (msg) => {
process.send(findMaxK(msg.n, msg.n + BATCH_SIZE));
});
}


Output on my 2019 MacBook Pro:

found A261865(12779527) = 134 in 0.299s
found A261865(2345213) = 187 in 0.308s
found A261865(63856063) = 193 in 0.33s
found A261865(222125822) = 210 in 0.681s
found A261865(237941698) = 217 in 0.687s
found A261865(257240414) = 227 in 0.804s
found A261865(1217775885) = 230 in 2.704s
found A261865(1205703469) = 267 in 2.704s
found A261865(1558293414) = 299 in 3.306s
found A261865(4641799364) = 303 in 13.002s
found A261865(6600656102) = 323 in 20.045s
found A261865(11145613453) = 335 in 36.774s
found A261865(20641456345) = 354 in 73.047s


The highest K my machine found within 60s was A261865(11145613453) = 335.

• 335 is a great score. – Anush Feb 27 at 21:46
• @Noodle9 Might to be to do with the way he's batching his calculations? He actually calculates 4xxxxxxx in parallel with 6xxxxxxx so he'll find 63xxxxxx before 46xxxxxx. – Neil Feb 27 at 22:25
• @Neil Yes, just tried with SageMath and got A(63856063) -> 193 as well as A(46272966) -> 193. – Noodle9 Feb 28 at 0:07

# C (gcc), Score 335 on TIO

#include <stdio.h>
#include <math.h>

int main() {

double n = 0, k;

while( n += 13 ) {

for(k = 2; ceil(sqrt((n + 1) * (n + 1) / k)) - floor(sqrt(n * n / k)) < 2; k++);

if( k > 250 ) printf("%.lf -> %.lf\n", n, k);
}

return 0;
}


Try it online!

The algorithm to compute A(n) is took from the OEIS page.

The n for which A(n) is being computed, follows the heuristics below:

I computed these first few A(n) greater than 100

   n    -> A(n)  | Factors of n
-------------------------------
130375 -> 118   | 5 5 5 7 149
169819 -> 127   | 13 13063
902236 -> 103   | 2 2 211 1069
1227105 -> 106   | 3 3 5 11 37 67
1793759 -> 105   | 11 179 911
1940874 -> 103   | 2 3 13 149 167
1962875 -> 105   | 5 5 5 41 383
2135662 -> 130   | 2 1067831
2345213 -> 187   | 13 13 13877
2470326 -> 111   | 2 3 411721
3461537 -> 115   | 3461537
4221630 -> 105   | 2 3 3 5 7 6701
4576794 -> 103   | 2 3 229 3331
5021205 -> 114   | 3 5 7 17 29 97
5396362 -> 110   | 2 2698181
8567238 -> 102   | 2 3 29 53 929
9182575 -> 103   | 5 5 89 4127
9983754 -> 102   | 2 3 3 11 50423


Where there are two notable local maximum: 127 and 187.

As you can see, in both cases the generating n is a multiple of 13, and that seemed to me a good enough reason to conjecture that, on average, multiples of 13 may generate an higher A(n) than most numbers of the same magnitude.

So I made a program to compute the multiples of 13 and leaving it running for a minute on TIO, the maximum I get is

11145613453 -> 335

• When I computed A(13^17) I got 5, not 498. Could there be an error in your code? – dingledooper Mar 1 at 10:05
• @dingledooper I tried it with the code of another answer and it gives 498 – Sheik Yerbouti Mar 1 at 10:55
• The answer I got says otherwise. Might it be possible that the other answer is also incorrect? – dingledooper Mar 1 at 11:14
• Yes, the actual result is 5, as evidenced by this Python code. Try it online! – user202729 Mar 1 at 12:22
• @dingledooper the algorithm is copied OEIS's page and is unlikely to be as broken as the math of your program. user202729 could you explain why your algorithm should work? Men if you don't like the "13 guess" just say it and if the OP thinks that my answer is invalid I will indeed delete it. – Sheik Yerbouti Mar 1 at 14:14

# Python 3, score $$\193\$$

from math import ceil, floor, sqrt

def f(n):
k = 2
while ceil(sqrt((n + 1)**2/k)) - floor(sqrt(n**2/k)) < 2:
k += 1
return k


Try it online!

Straight forward port of the Mathematica code on OEIS A261865 to get the ball rolling.

On my laptop (Intel(R) Core(TM) i7-8750H CPU @ 2.20 GHz with 16 GB RAM):

from functools import wraps
import errno
import os
import signal

class TimeoutError(Exception):
pass

def timeout(seconds=10, error_message=os.strerror(errno.ETIME)):
def decorator(func):
def _handle_timeout(signum, frame):
raise TimeoutError(error_message)

def wrapper(*args, **kwargs):
signal.signal(signal.SIGALRM, _handle_timeout)
signal.alarm(seconds)
try:
result = func(*args, **kwargs)
finally:
signal.alarm(0)
return result

return wraps(func)(wrapper)

return decorator

from math import ceil, floor, sqrt

@timeout(60)
def f():
n = 1
m = 1
while 1:
k = 2
while ceil(sqrt((n + 1)**2/k)) - floor(sqrt(n**2/k)) < 2:
k += 1
if k > m:
print(f'A({n}) -> {k}')
m = k
n += 1
f()


produces:

A(1) -> 2
A(3) -> 3
A(23) -> 7
A(30) -> 15
A(184) -> 38
A(8091) -> 43
A(16060) -> 46
A(16907) -> 58
A(20993) -> 61
A(26286) -> 97
A(130375) -> 118
A(169819) -> 127
A(2135662) -> 130
A(2345213) -> 187
A(46272966) -> 193
Traceback (most recent call last):
File "A261865_timeout.py", line 41, in <module>
f()
File "A261865_timeout.py", line 18, in wrapper
result = func(*args, **kwargs)
File "A261865_timeout.py", line 35, in f
while ceil(sqrt((n + 1)**2/k)) - floor(sqrt(n**2/k)) < 2:
File "A261865_timeout.py", line 12, in _handle_timeout
raise TimeoutError(error_message)
__main__.TimeoutError: Timer expired

• Note that the Python code in this answer suffers from a floating point errors that results in huge $k$ value for large input. Nevertheless the value reported by this answer is correct. – user202729 Mar 1 at 12:24

# C (clang), score 210 on TIO

#include <stdio.h>
int main() {
unsigned long long x, i, j, k;
for (x = 2; x < 222125823ULL; x++) {
for (i = 1; ; i++) {
for (j = 2; j * j * i <= x * x; j *= 2);
for (k = j / 2; k /= 2; ) if ((j - k) * (j - k) * i > x * x) j -= k;
if (j * j * i < (x + 1) * (x + 1)) break;
}
if (i > 99) {
printf("A261865(%llu)=%llu\n", x, i);
fflush(stdout);
}
}
}


Try it online! Calculates all A261865 entries from 2 to 222,125,822 in just under 60s on TIO. Annoyingly, it doesn't seem to be possible to reach 250,000,000 within the time limit. In any case it is limited to about 2,000,000,000 due to the use of 64-bit integer arithmetic (no square root operations). By switching to unsigned __int128 you could quickly calculate A261865 for specific higher values of course.

Edit: Just tried a threaded version on my local 16-core processor and it can reach 2,000,000,000 in just under 60 seconds, finding A261865(1558293414)=299. Soon after that it stops working because j reaches 4,294,967,296 and then j * j overflows to zero.

Edit: I left the 128-bit single-threaded version running overnight and it found the following record values for A261865:

A261865(3)=3 (0s)
A261865(23)=7 (0s)
A261865(30)=15 (0s)
A261865(184)=38 (0s)
A261865(8091)=43 (0s)
A261865(16060)=46 (0s)
A261865(16907)=58 (0s)
A261865(20993)=61 (0s)
A261865(26286)=97 (0s)
A261865(130375)=118 (0s)
A261865(169819)=127 (0s)
A261865(2135662)=130 (0.7s)
A261865(2345213)=187 (0.8s)
A261865(46272966)=193 (17.8s)
A261865(222125822)=210 (91.7s)
A261865(237941698)=217 (98.6s)
A261865(257240414)=227 (1.8m)
A261865(1205703469)=267 (8.9m)
A261865(1558293414)=299 (11.6m)
A261865(4641799364)=303 (34.9m)
A261865(6600656102)=323 (49.9m)
A261865(11145613453)=335 (85m)
A261865(20641456345)=354 (2.7h)
A261865(47964301877)=358 (6.3h)
A261865(105991039757)=385 (14.2h)
A261865(119034690206)=397 (16h)
A261865(734197670805)=455 (4.4d)

• I can read a comment of the OP saying that you should "compute one large value of A(n) within the time limit" rather all the A(n) till a certain maximum. Am I right to be confused? – Sheik Yerbouti Feb 27 at 20:37
• @SheikYerbouti I am also confused. I can easily adapt my code to calculate one value e.g. A261865(20641456345) in a fraction of a second. I don't know how I'm supposed to find a nice large value of A261865 to compute in the first place though... – Neil Feb 27 at 20:41
• I think that every answer here adopted this interpretation of finding all A(n) till a certain maximum. It surely is an easier way to score the answers, but if the OP won't aknowledge it, then your score would be inaccurate. (And you couldn't easily make an accurate one in C) – Sheik Yerbouti Feb 27 at 20:53
• @Anush Now 455! – Neil Mar 4 at 13:08
• @Anush Now 501! (on my other answer) – Neil Mar 7 at 12:16

# C (clang), score 299 on TIO

#include <stdio.h>
#define A261865 256
unsigned long long J[A261865], K[A261865];
int main() {
int i, m;
unsigned long long x, j, k;
for (i = 1; i < A261865; i++) J[i] = K[i] = i;
m = 2;
for (x = 1; x < 0x60000000ULL; x++) {
for (i = 1; ; i++) {
if (i < A261865) {
while (J[i] <= x * x) J[i] += K[i] += i + i;
if (J[i] < (x + 1) * (x + 1)) break;
} else {
for (j = k = i; j <= x * x; j += k += i + i);
if (j < (x + 1) * (x + 1)) break;
}
}
if (i > m) {
printf("A261865(%llu)=%d\n", x, i);
fflush(stdout);
m = i;
}
}
}


Try it online! Takes under 60s to output:

A261865(3)=3
A261865(23)=7
A261865(30)=15
A261865(184)=38
A261865(8091)=43
A261865(16060)=46
A261865(16907)=58
A261865(20993)=61
A261865(26286)=97
A261865(130375)=118
A261865(169819)=127
A261865(2135662)=130
A261865(2345213)=187
A261865(46272966)=193
A261865(222125822)=210
A261865(237941698)=217
A261865(257240414)=227
A261865(1205703469)=267
A261865(1558293414)=299


Using a version with a 128-bit integer type and larger square root cache, this code has found the following values on my PC:

A261865(3)=3 (0s)
A261865(23)=7 (0s)
A261865(30)=15 (0s)
A261865(184)=38 (0s)
A261865(8091)=43 (0s)
A261865(16060)=46 (0s)
A261865(16907)=58 (0s)
A261865(20993)=61 (0s)
A261865(26286)=97 (0s)
A261865(130375)=118 (0s)
A261865(169819)=127 (0s)
A261865(2135662)=130 (0s)
A261865(2345213)=187 (0s)
A261865(46272966)=193 (1s)
A261865(222125822)=210 (5.2s)
A261865(237941698)=217 (5.7s)
A261865(257240414)=227 (6.2s)
A261865(1205703469)=267 (31s)
A261865(1558293414)=299 (41.8s)
A261865(4641799364)=303 (2.1m)
A261865(6600656102)=323 (3m)
A261865(11145613453)=335 (5.2m)
A261865(20641456345)=354 (9.8m)
A261865(47964301877)=358 (22.9m)
A261865(105991039757)=385 (52m)
A261865(119034690206)=397 (59.1m)
A261865(734197670865)=455 (6.4h)
A261865(931392113477)=501 (8.4h)
A261865(1560674332481)=505 (14.2h)


It also found A261865(5928861186373)=509, but I wasn't able to run it continuously for the ~2 days needed, so I don't know how long it took.