18
\$\begingroup\$

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.)

\$\endgroup\$
10
  • 2
    \$\begingroup\$ 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? \$\endgroup\$
    – xash
    Feb 27, 2021 at 17:28
  • \$\begingroup\$ @xash, compute one large value of A(n) within the time limit. \$\endgroup\$ Feb 27, 2021 at 18:31
  • 2
    \$\begingroup\$ 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).) \$\endgroup\$ Feb 27, 2021 at 18:40
  • 1
    \$\begingroup\$ @Sheik, I updated the question to try to address any confusion. I hope this helps! \$\endgroup\$ Feb 28, 2021 at 7:18
  • 1
    \$\begingroup\$ I think that the next best answer is going to have something to do with continued fraction. \$\endgroup\$
    – DELETE_ME
    Mar 1, 2021 at 9:35

7 Answers 7

4
\$\begingroup\$

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
\$\endgroup\$
12
  • 1
    \$\begingroup\$ When I computed A(13^17) I got 5, not 498. Could there be an error in your code? \$\endgroup\$ Mar 1, 2021 at 10:05
  • \$\begingroup\$ @dingledooper I tried it with the code of another answer and it gives 498 \$\endgroup\$
    – anotherOne
    Mar 1, 2021 at 10:55
  • 1
    \$\begingroup\$ The answer I got says otherwise. Might it be possible that the other answer is also incorrect? \$\endgroup\$ Mar 1, 2021 at 11:14
  • \$\begingroup\$ Yes, the actual result is 5, as evidenced by this Python code. Try it online! \$\endgroup\$
    – DELETE_ME
    Mar 1, 2021 at 12:22
  • \$\begingroup\$ @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. \$\endgroup\$
    – anotherOne
    Mar 1, 2021 at 14:14
3
\$\begingroup\$

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[0] = sqrtl(2) / (sqrtl(2) - 1);
 steps[1] = 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] + 1; i < end / steps[1]; i++)
   chunk[(L)(i * steps[1]) - 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[0] + 1; i < end / steps[0]; i++) {
   L xi = (L)(i * steps[0]) - 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.

\$\endgroup\$
3
  • \$\begingroup\$ Why would this find A261865(557784208155) = 383 but not A261865(105991039757) = 385 or A261865(119034690206) = 397? \$\endgroup\$
    – Neil
    Feb 28, 2021 at 17:27
  • \$\begingroup\$ @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! \$\endgroup\$
    – xash
    Feb 28, 2021 at 17:36
  • \$\begingroup\$ @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. :-) \$\endgroup\$
    – xash
    Feb 28, 2021 at 18:03
3
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 335 is a great score. \$\endgroup\$
    – user7467
    Feb 27, 2021 at 21:46
  • \$\begingroup\$ @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. \$\endgroup\$
    – Neil
    Feb 27, 2021 at 22:25
  • \$\begingroup\$ @Neil Yes, just tried with SageMath and got A(63856063) -> 193 as well as A(46272966) -> 193. \$\endgroup\$
    – Noodle9
    Feb 28, 2021 at 0:07
3
\$\begingroup\$

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)
\$\endgroup\$
7
  • \$\begingroup\$ 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? \$\endgroup\$
    – anotherOne
    Feb 27, 2021 at 20:37
  • 1
    \$\begingroup\$ @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... \$\endgroup\$
    – Neil
    Feb 27, 2021 at 20:41
  • \$\begingroup\$ 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) \$\endgroup\$
    – anotherOne
    Feb 27, 2021 at 20:53
  • 1
    \$\begingroup\$ @Anush Now 455! \$\endgroup\$
    – Neil
    Mar 4, 2021 at 13:08
  • 1
    \$\begingroup\$ @Anush Now 501! (on my other answer) \$\endgroup\$
    – Neil
    Mar 7, 2021 at 12:16
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – DELETE_ME
    Mar 1, 2021 at 12:24
1
\$\begingroup\$

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

\$\endgroup\$
16
  • \$\begingroup\$ 399.....woohoo! \$\endgroup\$
    – user7467
    Feb 28, 2021 at 14:01
  • \$\begingroup\$ It's better to use printf when printing from multiple threads if you don't want to see the output all tangled together. \$\endgroup\$
    – xiver77
    Mar 11, 2022 at 4:26
  • \$\begingroup\$ @xiver77 No. Both cout.operator<<() and printf() send output to stdout the exact same way as far as multithreading is concerned.. \$\endgroup\$
    – Noodle9
    Mar 11, 2022 at 11:06
  • \$\begingroup\$ Well, since the standard doesn't define how cout and printf should work when called through multiple threads, it would depend on the implementation. It's a few years ago, but I remember printf was a fix for something like > for A261865(<2> for A261865(100000000001) in your output. It was because printf wrote to the buffer at one after finishing translating the format string, but cout was like multiple calls to printf. \$\endgroup\$
    – xiver77
    Mar 11, 2022 at 11:15
  • \$\begingroup\$ I checked your code through TIO, and it seems the implementation has improved that your output is not tangled. \$\endgroup\$
    – xiver77
    Mar 11, 2022 at 11:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.