I found this typo entertaining:
Technically it could be replaced by any other large prime number. The most important thing is that it must have few factors, and be large enough to distribute information into the higher value bits when the integer overflows.
Surely any prime number has "few factors", i.e. none other than itself and 1? I guess the "prime" in the first sentence is a typo, since the second sentence reads as if the first one didn't say "prime".
I haven't benchmarked it, but I think that should easily run in under a second on any phone sold in the last 10 years. If you do it a bit smarter and skip even divisors, I think it could run in under a second on 30 year old hardware (25k iterations, 200-ish cycles per loop (division was very expensive, back then) takes a 5MHz CPU)
(x+=x*x+9)>>32; x+=x*x+9;
x+=((x*x+9)>>32);
e.g:
uint64_t x = 0;
...
uint32_t y = (x+=x*x+9)>>32;