allocate mem(2^30)

\\ A001175	Pisano periods (or Pisano numbers): period of Fibonacci numbers mod n.
pic = Map()		\\ cache
pi(n) = {
	my (f=factor(n), v=1);

	for (k=1, #f~,
		my (pk = f[k,1]^f[k,2], p);
		if (!mapisdefined(pic, pk, &p),
			my (u=Mod(0,n), v=Mod(1,n));
			for (q=1, oo,
				[u,v]=[v,u+v];
				if (u==0 && v==1,
					mapput(pic, pk, p=q);
					break;
				);
			);
		);

		v = lcm(v, p);
	);

	return (v);
}

\\ period of k -> F(F(k)) mod n
\\ F(F(k)) mod n = F(F(k mod pi^2(n)) mod pi(n)) mod n
a(n) = {
	my (p=pi(n), p2=pi(p), f=vector(p2), ff=vector(p2));
	for (k=1, p2,
		f[k] = if (k==1, Mod(0, p),
		           k==2, Mod(1, p),
				         f[k-2]+f[k-1]);
		ff[k] = fibonacci(lift(f[k])) % n;
	);

	fordiv (p2, d,
		if (ff[1..p2-d]==ff[d+1..p2],
			return (d);
		);
	);
}

for (n=1, 10 000, print (n " " a(n)))

quit