login
A213407
First occurrence of n in A213381.
2
2, 0, 3, 5, 4, 9, 8, 7, 12, 17, 594270126787, 21, 20, 13, 24, 29, 16, 23, 32, 19, 36, 41, 1356, 45, 38, 151, 51, 411, 994, 57, 56, 31, 60, 65, 52, 69, 71, 37, 72, 77, 490, 81, 80, 169, 84, 6125, 68, 1043, 92, 49, 99, 101, 304, 105, 104, 55, 111, 63, 73, 89, 116, 61, 120, 125, 78, 129, 188, 67, 93, 137, 97, 18349355, 140, 433
OFFSET
0,1
FORMULA
a(n) = smallest k>n such that (-2)^k == n (mod k+2).
EXAMPLE
Smallest n such that A213381(n)=9 is 17, so a(9)=17.
PROG
(C)
#include <stdio.h> // GCC -O3 -fopenmp
#include <omp.h> // 11 minutes
#define SIZE 4096
#define STEP 0x1000000
long long first[SIZE];
int main(int argc, char **argv)
{
unsigned long long a, i;
for (a=0; a<SIZE; ++a) first[a]=-1LL;
omp_set_num_threads(4);
for (i=STEP; i<=0x100000000; i+=STEP) {
#pragma omp parallel for schedule(static, STEP/4)
for (a=i-STEP; a<i; ++a) {
unsigned long long b, r, p, t;
for (b=a+2, r=1, p=t=a; t>0; p=(p*p)%b, t>>=1) {
if (t&1) r=(r*p)%b;
}
if (r<SIZE) { if (a<(unsigned)first[r]) first[r]=a; }
}
printf("\n%llx : ", i);
for (a=0; a<SIZE; ++a) if (first[a]==-1LL) printf("%llu ", a);
}
printf("\n\n");
for (a=0; a<500; ++a) printf("%lld, ", first[a]);
}
CROSSREFS
KEYWORD
nonn
AUTHOR
Alex Ratushnyak, Jun 10 2012
EXTENSIONS
Terms a(10) onward from Max Alekseyev, Jan 31 2014
STATUS
approved