Certainly n+k must be even, since no odd number can be divisible by an even number.
The values of n+k = n+a(n) are given in the companion sequence A332584.
A heuristic argument suggests that k should always exist.
As of Jul 10 2020, up to n = 1000 there are just two unknown values, a(158) and a(539).
The following remarks summarize program made during the first half of 2020.
On Feb 19 2020 Joseph Myers discovered that a(98) = 259110640. On Feb 20 2020 he reported that a(44) > 10^11 if it exists; a(92), a(158) and a(170) are all > 10^10 if they exist; a(494), a(539), a(563), a(761), a(854), a(944) and a(956) are all > 2*10^9 if they exist; and that he has found all the other values up to a(1000). - N. J. A. Sloane, Feb 23 2020.
Added Feb 26 2020: Joseph Myers has now checked all the numbers up to 1000 out to a limit of 10^11 (see link).
Update from Paul Zimmermann, Mar 17 2020: (Start)
I started a parallel program using the same algorithm as in Joseph Myers's "grow.c" program on the few sequences with unknown status in http://oeis.org/A332580/a332580_2.txt.
This program just found:
pzimmermann@wurst:~/A332580$ tail 956.out
It thus seems that a(956) = 162236437060, i.e., the term of index n+k+1 is divisible by 162236438017 = 43 * 5051 * 746969.
Partial confirmation from Scott R. Shannon, Mar 17 2020: I set n = 956 and a k value a few less than 162236437060 in my Java version of Joseph Myer's program, and it found the results Paul Zimmermann gave. But that’s not much of a confirmation as it uses the same algorithm, just implemented in a different language.
Partial confirmation from Pierrick Gaudry, Mar 18 2020: (Start)
I ran the attached small C program in order to check that a(956) = 162236437060. More precisely, I check only that the 162236437060-th integer obtained starting with 956 is indeed 0 modulo 162236438017.
For this there is no need to rely on multi-precision arithmetic. However, since 162236438017 > 2^32, it not possible to use 64-bit arithmetic; or at least, it was easier to use the 128-bit arithmetic provided by the compiler.
The algorithm is then fairly simple: just compute iteratively the big number obtained by concatenating 956, 957, 958, ... and so on, and reduce all along the way modulo 162236438017. The result should be zero. This was tested on a few other known example.
After a bit more than 1 hour on my laptop, this indeed prints 0, thus confirming that a(956) <= 162236437060 (this simple method does not check if there is a smaller value).
Full confirmation for a(956) from Joseph Myers, Mar 18 2020: I restarted computations for 956 where I had stopped them before (at 101 * 10^9) and ran them up to 163 * 10^9; I also get 162236437060.
Update from Paul Zimmermann, Mar 22 2020: (Start)
Here are four more values to check, confirmed independently by Pierrick Gaudry:
a(44) <= 2783191412912
a(92) <= 218128159460
a(494) <= 2314160375788
a(854) <= 440578095296 (also k=587470935254 divides)
All four values were found with the "sieving" algorithm I described in an earlier email (see the Myers-Schroeppel-Shannon-Sloane-Zimmermann paper), sieving all primes up to 5000000000. Thus it is possible that smaller solutions exist.
Up to n=1000, the remaining cases where we have no bound at present are 158, 539, 761, 944.
a(761) <= 111508066823971. Now only 3 values remain up to n=1000 (158, 539, 944). Paul Zimmermann, Mar 23 2020
I restarted my exhaustive search for 92 where I had previously stopped it, and can confirm a(92) = 218128159460. - Joseph Myers, Mar 23 2020
The remaining values to check are:
a(44) <= 2783191412912
a(494) <= 2314160375788
a(761) <= 111508066823971
a(854) <= 440578095296. (Paul Zimmermann, Mar 24 2020)
Joseph Myers confirmed a(854)=440578095296 on Mar 26 2020.
Summary: As of Apr 15 2020, a(n) is known for all n <= 1000 except for four values where we have only an upper bound (44, 494, 539, and 761), and two values (158, 944) where all we know is that if k exists then it is greater than 10^15. See the table in the Links section. - Joseph Myers and Paul Zimmermann.
From Paul Zimmermann, Apr 17 2020: I have completed the full check for n=494 up to n+k=10^12. Thus C(494) >= 10^12-494. It took about 4 hours. The final check from 10^12 to 2314160375788+494+1 should take another 4-5 hours. (I don't want this comment to be lost, even though it will probably be replaced by something stronger very soon. - N. J. A. Sloane, Apr 17 2020)
From Paul Zimmermann, Apr 18 2020: (Start)
I confirm that C(44) = 2783191412912 and C(494) = 2314160375788. These were checked with a parallel version of Joseph's program (attached). For n=44 I ran the following script which submits 28 jobs checking each a range of 10^11 values:
for i in `seq 0 27`; do
kmin=`expr 1 + $i \* 100000000000`
kmax=`expr $kmin + 100000000000 - 1`
oarsub -p "cluster='grvingt'" -q production -l walltime=5 "./A332580 -kmin $kmin 44 $kmax"
The last job took a little less than 4 hours (wall clock time) on a 32-core cpu (64 virtual cores), thus it took a total of about 300 cpu days. (End)
From Paul Zimmermann, Apr 19 2020: C(944) <= 1032422879252.