Let us consider the expression M^M+1, where M is a positive integer.

It can be verified that M=3 is the least value for which 2² divides M^M+1.

Given that n is a positive integer, find the least value of M (in terms of n) for which M^M+1 is divisible by 2ⁿ.

25      33554432        16      18446744073709551616
26      67108864        16      18446744073709551616
27      134217728       16      18446744073709551616
28      268435456       16      18446744073709551616
29      536870912       16      18446744073709551616
30      1073741824      16      18446744073709551616
31      2147483648      16      18446744073709551616
32      4294967296      16      18446744073709551616
33      8589934592      16      18446744073709551616
34      17179869184     16      18446744073709551616
35      34359738368     16      18446744073709551616
36      68719476736     16      18446744073709551616
37      137438953472    16      18446744073709551616
38      274877906944    16      18446744073709551616
39      549755813888    16      18446744073709551616
40      1099511627776   16      18446744073709551616
41      2199023255552   16      18446744073709551616
42      4398046511104   16      18446744073709551616
43      8796093022208   16      18446744073709551616
44      17592186044416          16      18446744073709551616
45      35184372088832          16      18446744073709551616
46      70368744177664          16      18446744073709551616
47      140737488355328         16      18446744073709551616
48      281474976710656         16      18446744073709551616

from

10   for N=2 to 48

20     N2=2^N

30     for M=2 to 30

40       Mm=M^M

50       if Mm@N2=0 then print N,N2,M,Mm:cancel for:goto 80

60     next

80   next

Posted by Charlie on 2014-05-01 16:35:40