IBM Ponder this 2023 09 solution

The problem can be found here.
Since the solution has been posted on the website, here's my solution:
Q1 is simple, just calculate them directly:

```cpp
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    if(a<b) swap(a,b);
    while(b){
        a=a%b;
        swap(a,b);
    }
    return a;
}
int main(){
    int a=531;
    //for(int i=2;i<1000;++i) {int d=gcd(i,a);cout<<d<<", ";a=a+d;}
    int cnt=0, i=2;
    while(cnt<10) {int d=gcd(i,a);if(d==5){++cnt;cout<<"(i="<<i<<",a="<<a<<"),";} a=a+d;i++;}
    return 0;
}
```

The second question takes a little observation, though. It's easy to see that the result must be an odd number. 9 and 15 don't work from reasoning, and 21 works. Working backwards, it's not hard to find that when $a_1=801$, $d_{21}=21$. (Somehow the solution page omitted the answer to this question. Probably overlooked.)

The bonus question is much harder to solve without the right tools, because it requires factoring many very large integers. Here's the code that I used to solve it:

```python
import primefac as pf
import os
from datetime import datetime
file=open("result2309.txt","a")
start=datetime.now()
print("starting time:",start)
file.write("starting time:"+str(start)+"\n")
def gcd(a,b):
    while(b>0):
        a=a%b
        a,b=b,a
    return a
a=531
i=2
cnt=0
while(cnt<200):
  g=gcd(a,i)
  if g!=1:
    if g==5:
      cnt+=1
      print(f"#{cnt}: i={i},a={a}")
      file.write(f"#{cnt}: i={i},a={a}\n")
      file.flush()
      os.fsync(file)
    a+=g
    i+=1
    continue
  n=a-i
  m=a
  d=0
  f=0
  factors=pf.primefac(n, verbose=False,methods=(pf.ecm,))
  for factor in factors:
    d=factor-(i%factor)
    if d<m:
      m=d
      f=factor
  if f==5:
    cnt+=1
    print(f"#{cnt}: i={i},a={a}")
    file.write(f"#{cnt}: i={i},a={a}\n")
    file.flush()
    os.fsync(file)
  a+=m
  i+=m
  #print(f"next one: (i={i},a={a})")
  a+=f
  i+=1
end=datetime.now()
print("ending time:",end)
print(str(end-start))
file.write("ending time:"+str(end)+"\n")
file.write(str(end-start)+"\n")
file.close()
```

It requires the package "primefac" installed.
The "ECM" is much faster than the default "pollardrho_brent" method for extremely large numbers. The default method took around 10 hours, while the ECM took about 17 minutes.

I'll update the logic behind the code when I have more time... Or you may find the paper linked on their solution page helpful.