text:
Code-Challenge: Farey sequence (II)
Challenge

In this task you would be given an integer N
  (less than 10^6), output the number of terms in the Farey
  sequence of order N.

The input N < 106 is given in a single line, the inputs are terminated by EOF.
The challenge is to implement the fastest solution so that it can process a maximum of 106-1 values as fast as possible.
Input
7
10
999
9999
79000
123000

Output
19
33
303793
30393487
1897046599
4598679951

Constraints

You can use any language of your choice
Take care about your fingers, do not use more than 4096 bytes of code.
Fastest solution, based on the running time measured for N = 106-1.

Are you going to be timing each single submission in the same environment?!

@J B:I guess the complexity only can do the trick,checking each submission in the same environment will probably give the same result.

The complexity can be O(1) because the input size is limited so we can pre-compute a lookup table...

@Peter Taylor:Thanks,for pointing that out,I have updated the constraints.

C - 0.1 Secs on Ideone
http://www.ideone.com/E3S2t
Explanation included in code.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long long A[1000001]={0};
int main()
{
    int isprime[1001],d,n,k,i,e,p;

    for (n=2;n<1001;n++)
        isprime[n]=1;

    //Sieve of Eratosthenes for Prime
    //Storing the smallest prime which divides n.
    //If A[n]=0 it means it is prime number.
    for(d=2;d<1001;d++)
    {
        if(isprime[d])
        {
            for (n=d*d;n<1001;n+=d)
            {
                isprime[n]=0;
                A[n]=d;
            }
            for (;n<=1000000;n+=d)
                A[n]=d;
        }
    }

    //Uses multiplicative property of
    //Euler Totient Function
    //Phi(n)=Phi(p1^k1)*Phi(p2^k2)...*Phi(pr^kr)
    //and Phi(pi^ki)=(pi-1)*(pi^(ki-1))
    A[1]=1;
    for(n=2;n<=1000000;n++)
    {
        if (A[n]==0)
           A[n]=n-1;
        else
        {
           p=A[n],k=n/p,e=1;
           while (k%p==0)
                 k/=p,e*=p;
           A[n]=A[k]*e*(p-1);
        }
    }
    //Number of terms in Farey Series
    //|F(n)| = 1 + Sigma(i,1,n,phi(i))
    A[1]=2;
    for(n=2;n<=1000000;n++)
        A[n]+=A[n-1];

    while (~scanf("%d",&i))
        printf("%lld\n",A[i]);
    return 0;
}

A little more explanation:

For all numbers we get a prime factor
  of it from the sieve(or 0 if it is a
  prime). Next we use the fact that ETF
  is multiplicative. That is if m and n
  are coprime then
  phi(m*n)=phi(m)*phi(n). Here we take
  out the multiple of prime factor out
  and hence the left part and the
  multiple part are co-prime. We already
  have the ETF for the left part since
  it is either smaller then current
  value or equal to 1. We only need to
  calculate the ETF for the multiple
  which we calculate using the formula
  phi(pi^ki)=(pi-1)*(pi^(ki-1)).

Between,you approach is slight faster than mine ... would you like to elaborate the implementation,precisely the ETF computation part,theoretically I understand though.

Ah yes, of course, individual prime factorization like I did is a waste of time.

C - Less than a second for 999999
#include "stdio.h"
#include "time.h"
#define i64 unsigned long long
#define i32 unsigned int
#define PLIM 1100
#define FLIM 1000000

i32 primes[PLIM];
i64 f[FLIM];

int main(int argc, char *argv[]){
    i64 start=clock();
    i32 primesindex=0;
    f[0]=1;
    f[1]=2;
    i32 a,b,c;
    i32 notprime;
    //Make a list of primes
    for(a=2;a<PLIM;a++){
        notprime=0;
        for(b=0;b<primesindex;b++){
            if(!(a%primes[b])){
                notprime=1;
            }
        }
        if(!notprime){
            primes[primesindex]=a;
            primesindex++;
        }
    }
    i32 count,divided;
    i32 nextjump=4;
    i32 modlimit=2;
    i32 invalue;
    a=2;
    for(c=1;c<argc;c++){
        invalue=atoi(argv[c]);
        if(invalue<FLIM && invalue){
            //For each number from a to invalue find the totient by prime factorization
            for(;a<=invalue;a++){
                count=a;
                divided=a;
                b=0;
                while(primes[b]<=modlimit){
                    if(!(divided%primes[b])){
                        divided/=primes[b];
                        //Adjust the count when a prime factor is found
                        count=(count/primes[b])*(primes[b]-1);
                        //Discard duplicate prime factors
                        while(!(divided%primes[b])){
                            divided/=primes[b];
                        }
                    }
                    b++;
                }
                //Adjust for the remaining prime, if one is there
                if(divided>1){
                    count=(count/divided)*(divided-1);
                }
                //Summarize with the previous totients
                f[a]=f[a-1]+(i64)count;
                //Adjust the limit for prime search if needed
                if(a==nextjump){
                    modlimit++;
                    nextjump=modlimit*modlimit;
                }
            }
            //Output result
            printf("%I64u\n",f[invalue]);
        }
    }
    i64 end=clock();
    //printf("Runtime: %I64u",end-start);
    return 0;
}

This takes input from command line.
The computation is a simple sum of totients, it's only done once and only up to the biggest input.
Here is an Ideone version: http://www.ideone.com/jVbc0

Just for the sake of competition Please elaborate your approach precisely the ETF computation and you may  like to change a bit so that IDEONE testing could be done :-)

The link doesn't work.

C (0.2 sec in Ideone)
I thought of adding my approach too: (this is not as fast as Gaurav's)
 #include <stdio.h>
 #define N 1000000
 long long Phi[N+1];

 //Sieve ETF

int main(){
   int i,j;

 for(i=1;i<=N;i++)
    Phi[i]=i;

 for(i=2;i<=N;i++){
    if(Phi[i] == i)
       for(j=i;j<=N;j+=i)
           Phi[j] = (Phi[j]/i)*(i-1);
  }

int t,n;

 Phi[1]=2;
 for(i = 2; i < N; i++)
     Phi[i] += Phi[i-1];

for(;~scanf("%d",&n);)
    printf("%lld\n",Phi[n]);

return 0;
}

TESTING ...

J, 0.2s, short code
It feels weird to write ungolfed J, but it actually is the language for the task, for once.
input =: ". ;. _2 stdin ''
phi =: 5 & p:
max =: >. / input
acc_totient =: +/ \ phi >: i. max
output =: >: (<: input) { acc_totient
echo output

Reads input, constructs accumulated sum of totients up to the max, and reads output from there.

Wow, for a second I thought that code might actually be readable, but the input line at least doesn't make any sense despite the result being stored in an appropriately named variable. :-P

@eBusiness: aww, c'mon ;) stdin '' reads and returns the entire input.  ;. _2 applies the verb on its left to the argument on its right, split line by line.  The verb on its left ". converts a string to a J noun, it our case a number.  Would it be more readable to you as input =: ; do each cutLF stdin '' ?

I would,'t say that it's very clear, but using word commands does seem to make it look just a tad bit more familiar.

FWIW, I find it hugely less readable, but that's mostly because it does the same in a more convoluted way (unnecessary boxing and unboxing).  Unfortunately, I couldn't find word commands for such simple actions.

VB.NET, 0.11 s for 10^6
This is basically a totient computation using prime sieve. The time is measured 10 times and the average is computed.
Module Module1

Sub Main()
    Dim sw As New Stopwatch
    Dim M As Integer = Console.ReadLine()
    sw.Start()

    Dim is_prime(M) As Integer
    Dim phi(M) As Integer

    For i = 0 To M
        phi(i) = i
        is_prime(i) = True
    Next

    For i = 2 To M
        If is_prime(i) = True Then
            phi(i) = i - 1
            Dim j As Integer = 2 * i
            Do Until j > M
                is_prime(j) = False
                phi(j) = phi(j) - (phi(j) / i)
                j += i
            Loop
        End If
    Next

    Dim result As Long = 1
    For i = 1 To M
        result += phi(i)
    Next

    Console.WriteLine(result)
    sw.Stop()
    Console.WriteLine("Time Elasped : " & sw.ElapsedMilliseconds)
    Dim a = Console.ReadLine()
End Sub

End Module

Welcome to PPCG!

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/2.5/


text:
Help Mr Jones to enjoy his bicycle round-trip
Mr Jones wants to do a round-trip on his bicycle. He wants to visit several cities in arbitrary order, but his route must not cross it self, since he hates to be at the same place twice in his holidays. As he really loves cycling, the length of his route is completely irrelevant, but he dislikes to drive around the landscape without a target. The route he likes is from on city in a straight line to another, without any detour.
As Mr Jones is a passionated code golfer, he wants you to find a program, that plans a round trip for him, given a set of cities. The input has the form A (B|C). A is a city's name, B and C are its coordinates. You may assume, that the coordinate are positive and less than 1000. The data sets for the cities are line-separated. Here is an example, of how an example input might look like:

SomeTown (1|10)
ACity (3|4)
Wherever (7|7)
Home (5|1)

Mr Jones isn't pedantic, he just wants to have a useful program. Thus, you may decide by your self how the output is looking like, as long as it mets these criteria:

The output is a map of the cities, with the route drawn between them. If anything is correct, the route shouldn't overlap itself and should end where it started
The coordinates are like in usual programming: (1|1) is in the NW corner. Add kind of a ruler to the maps border, to ease reading it
The cities names have to be written down on the map, but feel free to use abbreviations which is explained somewhere else on the map
The map can be both ASCII-art or an image
Keep the output readable

An output might look like this:

  1234567
 1    D
 2   * *
 3  *  *
 4  B   *
 5  *   *
 6  *   *
 7 *    C
 8*   **
 9*  *
10A**

A: SomeTown
B: ACity
C: Wherever
D: Home

The program with the smallest char count wins. I don't count parameters to the compiler / interpreter, if they are needed for compiling, but please don't abuse this rule. Usual code golf rules apply.
Here is another testcase. You output doesn't have to match mine, nor do you have to choose the same path as me. The output is drawn by hand and shows a possible output. Input:

home (5|7)
supermarket (13|12)
park (15|5)
new plaza (9|16)
friend's house (20|11)
old castle (14|21)
riverside (1|20)
beach (10|1)
cinema (21|18)
forest (23|7)
little island (21|1)
museum of code-golf (6|25)
airport (18|25)
tea-shop (24|14)
restaurant (24|22)
great bridge (3|12)
SO building (25|9)

And this is an example output:

           1111111111222222
  1234567890123456789012345
 1         H*        *K
 2        *  *      *  *
 3        *   *    *   *
 4       *     * **    *
 5      *       C      *
 6     *               *
 7    A                 J
 8   *                   *
 9   *                    Q
10   *                    *
11   *            ***E    *
12  P         B***   *   *
13  *        *       *   *
14  *       *        *   N
15 *       *          *  *
16 *      D           *  *
17 *       *          *  *
18*         *         I  *
19*          *        *  *
20G           *      *   *
21 *           F     *   *
22  *         **    *    O
23   *      **     *   **
24    *   **       *  *
25     L**         M**

A: home
B: supermarket
C: park
D: new plaza
E: friend's house
F: old castle
G: riverside
H: beach
I: cinema
J: forest
K: little island
L: museum of code-golf
M: airport
N: tea-shop
O: restaurant
P: great bridge
Q: SO building

I am not an English native speaker. Feel free to correct my language and grammar, if necessary.

J, 357 288
m=:>:>./c=:>1{"1 p=:([:<`([:<1-~[:".;._1'|',}:);._1'(',]);._2(1!:1)3
'n c'=:|:o=:p/:12 o.j./"1 c-"1(+/%#)c
C=:<"1 c
L=:u:65+i.#o
g=:<"1;c([:<@|:0.5<.@+[+>@])"1(-~/"2(<@:*]%~i.@>:@])"0([:>./|@-/)"2)>C,"0(1|.C)
echo(u:48+10|i.>:0{m),|:(u:48+10|>:i.1{m),L C}'*'g}m$' '
echo' ',L,.':',.' ',.n

This is just a quick squeezing of the original (see below). A lot of golfing is probably still possible to eliminate lots of useless rank manipulation and boxing.
Only caveat: Ruler is just the last digit unlike example output.
Edit: Bug fix - Cities had wrong labels (and were not in alpha order on map).
Edit 2: Removed all sorts of horseplay and tomfoolery for a savings of 69 characters.
Output (Verbatim, from test script):
First example:
01234567
1    B
2   **
3   * *
4  A  *
5  *  *
6 *    *
7 *    C
8 *  **
9* **
0D*

A: ACity
B: Home
C: Wherever
D: SomeTown

Second example:
012345678901234567890123456789012
1         D          F
2        * *       ***
3       *   **    *  *
4       *     * **   *
5      *       E     *
6     *              *
7    C              *          *I
8     **            *      *****
9       *           *   *H*   *
0        **         * **     *
1          **       G*     **
2  A*********B            *
3   **                   *
4     *                 J
5      **              *
6        Q             *
7      **             *
8    **              K
9  **                 *
0P*                    *
1 *           N        *
2  *        ** *        L
3   *     **    *     **
4    *  **       *  **
5     O*          M*

A: great bridge
B: supermarket
C: home
D: beach
E: park
F: little island
G: friend's house
H: SO building
I: forest
J: tea-shop
K: cinema
L: restaurant
M: airport
N: old castle
O: museum of code-golf
P: riverside
Q: new plaza
   End Second

Ungolfed original:
coords =: > 1 {" 1 parsed =: ([:<`([:<[:".;._1'|',}:);._1'(',]);._2 (1!:1)3

center =: (+/%#) coords
max =: >:>./ coords
angles =:  12 o. j./"1 coords -"1 center
ordered =: parsed /: angles
paths =: >(],"0(1)|.]) 1 {" 1 ordered

path_grid_lengths =: ([:>./|@-/)"2 paths
path_grid_interval =: ([:<]%~i.@>:@|)"0 path_grid_lengths
path_grid_distances =: -~/"2 paths
path_grid_steps =: path_grid_distances ([:<[*>@])"0 path_grid_interval

path_grid_points_sortof =: (> 1{"1 ordered) ([:<0.5<.@+[+>@])"0 path_grid_steps
path_grid_points =: <"1;([:<>@[,.>@])/"1 path_grid_points_sortof

graph_body =: }."1}. (u:65+i.#ordered) (1{"1 ordered) } '*' path_grid_points} max $ ' '

axis_top =: |:(":"0)10|}.i. 1{max
axis_side =: (":"0)10|i. 0{max

echo |:(axis_side) ,"1 axis_top, graph_body
echo ''
echo (u:65+i.#parsed),.':',.' ',.(> 0{"1 ordered)

You know, the question states, that the output is mostly freeform, so you don't have to keep a specific order of the labels.

@FUZxxl: It's not the order, it's that the cities were labeled wrong (wrong positions)

You win. (15 chars)

...15 chars? What's 15 chars?

A comment has to have at least 15 chars. Since I wanted to tell you, that you won my task, and the plain message »You win.« is shorter then 15, I had to add this text.

Well, I'm glad we had this little talk.

Haskell, 633 characters
import List
c n=n>>=(++" ").show.(*3)
(x&y)l="<text x='"++c[x]++"' y='"++c[y]++"'>"++l++"</text>"
f%p=[a-1,b+2,(a+b)/2]where n=map(f.fst)p;a=minimum n;b=maximum n
s p=concat["<svg xmlns='http://www.w3.org/2000/svg' viewBox='",c[i,m-1,j,n],"'><polygon fill='none' stroke='#c8c' points='",c$snd=<<(sort$map a p),"'/><g font-size='1' fill='#bbb'>",(\x->(x&m$show x)++(i&x$show x))=<<[floor(i`min`m)..ceiling(j`max`n)],"</g><g font-size='2'>",snd=<<p,"</g></svg>"]where a((x,y),_)=(atan2(x-q)(y-r),[x,y]);[i,j,q,m,n,r]=fst%p++snd%p
w(l,s)=((x,y),(x&y)l)where(x,r)=v s;(y,_)=v r
v=head.reads.tail
main=interact$s.map(w.break(=='(')).lines

Rather longish for code-golf, but produces a lovely SVG map:

Or, if your browser can't handle SVG, a PNG of that image:

Edit: (648 -> 633) in-line coordinate drawing, and possibly draw more than needed, letting them be clipped by the viewBox; also a few golf-tricks here and there.

How about stripping the xmlns stuff? Some viewers don't need it.

No browser I have will display the SVG w/o the xmlns declaration.

Hm... at least eyes of gnome will do. (Though it isn't a browser)

Python, 516 476 bytes
#!/usr/bin/python
#coding=utf-8
import sys
H=V=0
T=[]
k=65
for L in sys.stdin.readlines():
 i,j,K=L.find('('),L.find('|'),'%c'%k
 n,h,v=L[:i-1],int(L[i+1:j]),int(L[j+1:-2])
 H=max(H,h);V=max(V,v);T+=[(K,h,v)];k+=1;print K+':',n
V=V+1&~1
for s in zip(*['%3d'%(i+1)for i in range(H)]):print'   '+''.join(s)
C=H*V*[u'─']
C[0::H]=u'│'*V
C[1::H]=V/2*u'└┌'
C[H-1::H]=V/2*u'┐┘'
C[0:2]=u'┌─'
C[-H:-H+2]=u'└─'
for K,h,v in T:C[v*H-H+h-1]=K
for i in range(V):print'%3d'%(i+1)+''.join(C[i*H:i*H+H])

(Note: I didn't include the first two lines in the byte count, I consider them "interpreter parameters".  But I did charge myself for the utf-8 length of the program in bytes.)
On your second example I produce:
A: home
B: supermarket
C: park
D: new plaza
E: friend's house
F: old castle
G: riverside
H: beach
I: cinema
J: forest
K: little island
L: museum of code-golf
M: airport
N: tea-shop
O: restaurant
P: great bridge
Q: SO building

            11111111112222222222333
   12345678901234567890123456789012
  1┌────────H──────────K──────────┐
  2│┌─────────────────────────────┘
  3│└─────────────────────────────┐
  4│┌─────────────────────────────┘
  5│└────────────C────────────────┐
  6│┌─────────────────────────────┘
  7│└──A──────────────────────────J
  8│┌─────────────────────────────┘
  9│└──────────────────────Q──────┐
 10│┌─────────────────────────────┘
 11│└─────────────────E───────────┐
 12│┌P─────────B──────────────────┘
 13│└─────────────────────────────┐
 14│┌─────────────────────N───────┘
 15│└─────────────────────────────┐
 16│┌──────D──────────────────────┘
 17│└─────────────────────────────┐
 18│┌──────────────────I──────────┘
 19│└─────────────────────────────┐
 20G┌─────────────────────────────┘
 21│└───────────F─────────────────┐
 22│┌─────────────────────O───────┘
 23│└─────────────────────────────┐
 24│┌─────────────────────────────┘
 25│└───L───────────M─────────────┐
 26└──────────────────────────────┘

Yay, Unicode glyphs!

Ooo... that's not how i'd like my bicycle trip. Originally, I planned to allow the shortest route between two cities only, but I forgot this restriction. If you agree, I'd like to rewrite the question, so that only direct routes between two cities are allowed.

Sure, that would be fine.  It's not a cash prize :)

Thanl you very much. I am very sorry for making your entry wrong, you get a special price instead.

Python, 1074 bytes
Ok, spent way too many bytes (and time) getting reasonable paths to work.
#!/usr/bin/python
#coding=utf-8
import sys
H=V=0
T=[]
k=65
R=1000
for L in sys.stdin.readlines():
 i,j,K=L.find('('),L.find('|'),'%c'%k
 n,h,v=L[:i-1],int(L[i+1:j]),int(L[j+1:-2])
 H=max(H,h);V=max(V,v);T+=[(v*R-R+h-1,K)];k+=1;print K+':',n
for s in zip(*['%3d'%(i+1)for i in range(H+1)]):print'   '+''.join(s)
T.sort()
U=reduce(lambda a,x:a[:-1]+[(a[-1][0],x)]if x/R==a[-1][0]/R else a+[(x,x)],[[(T[0][0],T[0][0])]]+map(lambda x:x[0],T))
C=R*V*[' ']
r=0
for x,y in U:C[x:y]=(y-x)*u'─'
for (a,b),(c,d)in zip(U,U[1:]):
 if r:
  if d%R>b%R:x=b/R*R+d%R;C[b:x]=(x-b)*u'─';C[x:d:R]=(d-x)/R*u'│';C[x]=u'┐'
  else:x=d/R*R+b%R;C[d:x]=(x-d)*u'─';C[b:x:R]=(x-b)/R*u'│';C[x]=u'┘'
 else:
  if c%R<a%R:x=a/R*R+c%R;C[x:a]=(a-x)*u'─';C[x:c:R]=(c-x)/R*u'│';C[x]=u'┌'
  else:x=c/R*R+a%R;C[a:x:R]=(x-a)/R*u'│';C[x:c]=(c-x)*u'─';C[x]=u'└'
 r^=1
p=U[0][1];C[p:H]=(H-p)*u'─'
if r:p=U[-1][1];C[p:R*V]=(R*V-p)*u'─'
else:V+=1;C+=[' ']*R;p=U[-1][0]+R;C[p:R*V]=(R*V-p)*u'─';C[p]=u'└'
C[H::R]=u'┐'+u'│'*(V-2)+u'┘'
for p,K in T:C[p]=K
for i in range(V):print'%3d'%(i+1)+''.join(C[i*R:i*R+H+1])

Makes nice paths, though:
A: SomeTown
B: ACity
C: Wherever
D: Home

   12345678
  1  ┌─D──┐
  2  │    │
  3  │    │
  4  B───┐│
  5      ││
  6      ││
  7┌─────C│
  8│      │
  9│      │
 10A──────┘

and
A: home
B: supermarket
C: park
D: new plaza
E: friend's house
F: old castle
G: riverside
H: beach
I: cinema
J: forest
K: little island
L: museum of code-golf
M: airport
N: tea-shop
O: restaurant
P: great bridge
Q: SO building

            111111111122222222223333
   123456789012345678901234567890123
  1         H──────────K───────────┐
  2         │                      │
  3         │                      │
  4         │                      │
  5         └────C────────────────┐│
  6                               ││
  7    A──────────────────────────J│
  8    │                           │
  9    └───────────────────Q       │
 10                        │       │
 11  ┌────────────────E────┘       │
 12  P─────────B──────────┐        │
 13                       │        │
 14        ┌──────────────N        │
 15        │                       │
 16        D───────────┐           │
 17                    │           │
 18┌───────────────────I           │
 19│                               │
 20G────────────┐                  │
 21             F                  │
 22             └─────────O        │
 23                       │        │
 24                       │        │
 25     L───────────M─────┘        │
 26     └──────────────────────────┘

That one is nice, though it doesn't use the shortest connection possible`between two cities.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/2.5/

sort: votes


text:
Code-Golf: Lights Off!
The shortest code to pass all possibilities wins
Many grid based games have been made that start off with a grid of lights that are switched on.  Pressing any of the lights causes that light and the four lights adjacent to it to be toggled.  When a light is toggled, it is turned off or turned on, depending on if it was intially turned on or off.  The goal is to hit the lights in a sequence that results in all of the lights being turned off at the end.
"X" represents lights that are turned on.  "O" represents lights that are turned off.  "P" represents that square that is pressed.
XOO          XOO      XOX      XOX      XXX
XOX          XOP  ->  XXO  ->  OPO  ->  XOX
OOX          OOX      POO      XXO      XOO

Intial Grid  Press 1  Press 2  Press 3  Ending Grid

Input can be taken directly from a file passed as an argument, or as standard input.  The first line of input will contain x (1 <= x <= 20), the size of the grid of lights, meaning x by x.  The second line will contain y (0 <= y <= (x * 3)2), the number of lights initially lit up.  The next y lines contain coordinates of lit up lights on the grid, in the format of "row column".  Lights that are already switched on (have been toggled previously) should be toggled off again.  The next line will contain z, the number of lights pressed.  The final z lines contain coordinates of the pressed lights, in the order that they were pressed, in the format of "row column".
No input will be incorrect.  All numbers will be within the given boundaries of the grid.
The output will be the final grid after all lights have been toggled.  It should be an n by n grid.  For each area that has a light which is on, the uppercase character "X" should be used.  For each area that has a light which is off, the uppercase character "O" should be used.
Lights that are affected that are off the grid should be ignored.  Toggling a light on the edge of a grid should only affect the lights that are on the grid itself.
Test Cases

Input
4
5
2 3
2 4
3 1
3 4
4 3
7
3 3
4 4
3 4
4 2
4 1
2 2
3 2

Output
OXOO
XOXO
XOXO
OXOO

Input
1
3
1 1
1 1
1 1
2
1 1
1 1

Output
X

J, 132
'x f'=:0 2{,i=:".;._2(1!:1)3
echo u:79+9*}:"1}."1}.}:2|+/(1:`[`]}&(0$~,~x+2))"0<"1(f{.2}.i),;([:<[,[:|:(2 4$0 0,,~1 _1)+])"1(3+f)}.i

Probably can be golfed a lot further.

Console only, stdin->stdout. Tested on j602 on Linux.
Passes both tests given.
Assumes sane upper limit on X (no extended precision)

Original ungolfed version:
NB. Whole input as two column grid
i=:".;._2(1!:1)3

NB. x is x, f is number of initial toggles
'x f'=:0 2{,i

NB. z is 1..x
z =: >:i.x

NB. Take a boxed pair of indices, generate 'cross' indices (boxed)
f2=:3 :'y,,<"1(>y)+"1>0 1;1 0;0 _1;_1 0'

NB. List of initial toggles, individually boxed
init=: <"1 f {. 2 }. i

NB. List of Ps, individually boxed
toggle=: <"1 (3 + f) }. i

NB. Grid of 0s padded on all sides
g =:0$~(x+2),(x+2)

NB. For each initial toggle, make a grid with a 1 in that position. Sum each 'position'.
grid =: +/ (1:`[`]}&g)"0 init

NB. For each position in the cross (f2) of each press, make a grid with a 1 in that position.
NB. Sum each 'position', add to 'grid', take mod 2, and select inner rows/columns.
gfinal =: z {"1 z { 2|grid + +/ (1:`([:f2[)`]}&g)"0 toggle

NB. Translate 0/1 to O/X through ascii and print
echo u:79+9*gfinal

Python, 209 203 199 characters
I=input
x=I()+1
s=0
C=lambda:eval(raw_input().replace(' ','*%d+'%x))
exec's^=1<<C();'*I()
exec's^=1+(7<<x)/2+(1<<x<<x)<<(C()-x);'*I()
R=range(1,x)
for r in R:print''.join('OX'[s>>r*x+c&1]for c in R)

The state of the lights is kept in a single (big) integer variable, s.  XORs with bitmasks are used to toggle the lights.  I keep an extra bit per row to prevent wraparound.

A masterpiece! So much can be learnt from here.

exec is a keyword, not a builtin function (in Python 2.x), so no need for those extra parentheses.

Ruby 1.9, 167 characters
n=gets.to_i
y=z=[*[1]*n,0]*n
$<.map{|i|a,b=i.split.map &:to_i;b ?[*y&&[b>1&&-1,b<n&&1,a>1&&~n,a<n&&n+1],0].map{|f|f&&z[n*a+a-n-2+b+f]*=-1}:y=!y}
z.map{|a|putc"
OX"[a]}

Edits:

(198 -> 191) Removed some unnecessary stuff
(191 -> 180) Simplified the way the input is parsed
(180 -> 172) Removed parentheses, use z[u]*=-1 instead of z[u]=-z[u], remove unused variable
(172 -> 169) Some simplifications
(169 -> 167) Simplified a conditional

Perl, 139 chars
@s=1..<>;<>=~/ /,$f{$`,$'+0}=1for 1..<>;<>=~/ /,map$f{$`+$_*($_&1),$'+int$_/2}^=1,-2..2for 1..<>;$\=$/;for$x(@s){print map$f{$x,$_}?X:O,@s}

Explanation:
# Read size and generate an array of integers from 1 to the size.
# We’ll need to iterate over this array often, but otherwise we don’t need the size
@s = 1..<>;

# Read number of prelit lights
for (1..<>) {
    # Find the space; sets $` and $' to row and column, respectively
    <> =~ / /;
    # Set the relevant light; need +0 because $' includes the newline
    $f{$`, $'+0} = 1;
}

# Read number of light switchings
for (1..<>) {
    # As above
    <> =~ / /;
    # Some nice formulas that flip the 5 relevant lights,
    # including the ones “off the board”, but we don’t care about those
    map {
        $f{ $`+$_*($_&1), $'+int$_/2 } ^= 1
    }, (-2..2);
}

# Cause each subsequent print statement to print a newline after it
$\ = $/;

# For each row...
for $x (@s) {
    # Print X’s and O’s as required
    print map { $f{$x,$_} ? X : O }, @s;
}

APL (71)
'OX'[1+⊃{⍵≠(⍳⍴⍵)∊(⊂⍺)+K,⌽¨K←(0 1)(0 0)(0 ¯1)}/({⎕}¨⍳⎕),⊂({⎕}¨⍳⎕)∊⍨⍳2/⎕]

Can you provide a hex dump for this?

@KevinBrown: It's just Unicode. What format do you want? The 5 blocks are actually called 'quads' and are supposed to look like that.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Non trivial powers
Write the shortest program to print the non-trivial powers ≤ 2^12 in order
non-trivial power means the base and exponent are > 1
Leading whitespace is optional
When there are multiple solutions, the order is not important, so
16 = 4^2, 2^4 is ok
Sample output:
      4 = 2^2
      8 = 2^3
      9 = 3^2
     16 = 2^4, 4^2
     25 = 5^2
     27 = 3^3
     32 = 2^5
     36 = 6^2
     49 = 7^2
     64 = 2^6, 4^3, 8^2
     81 = 3^4, 9^2
    100 = 10^2
    121 = 11^2
    125 = 5^3
    128 = 2^7
    144 = 12^2
    169 = 13^2
    196 = 14^2
    216 = 6^3
    225 = 15^2
    243 = 3^5
    256 = 2^8, 4^4, 16^2
    289 = 17^2
    324 = 18^2
    343 = 7^3
    361 = 19^2
    400 = 20^2
    441 = 21^2
    484 = 22^2
    512 = 2^9, 8^3
    529 = 23^2
    576 = 24^2
    625 = 5^4, 25^2
    676 = 26^2
    729 = 3^6, 9^3, 27^2
    784 = 28^2
    841 = 29^2
    900 = 30^2
    961 = 31^2
   1000 = 10^3
   1024 = 2^10, 4^5, 32^2
   1089 = 33^2
   1156 = 34^2
   1225 = 35^2
   1296 = 6^4, 36^2
   1331 = 11^3
   1369 = 37^2
   1444 = 38^2
   1521 = 39^2
   1600 = 40^2
   1681 = 41^2
   1728 = 12^3
   1764 = 42^2
   1849 = 43^2
   1936 = 44^2
   2025 = 45^2
   2048 = 2^11
   2116 = 46^2
   2187 = 3^7
   2197 = 13^3
   2209 = 47^2
   2304 = 48^2
   2401 = 7^4, 49^2
   2500 = 50^2
   2601 = 51^2
   2704 = 52^2
   2744 = 14^3
   2809 = 53^2
   2916 = 54^2
   3025 = 55^2
   3125 = 5^5
   3136 = 56^2
   3249 = 57^2
   3364 = 58^2
   3375 = 15^3
   3481 = 59^2
   3600 = 60^2
   3721 = 61^2
   3844 = 62^2
   3969 = 63^2
   4096 = 2^12, 4^6, 8^4, 16^3, 64^2

There's a lot of powers missing here; what about 21^3 etc?
What is your definition of "non-trivial powers"?

Is it also possible to print multiple lines with the same number on the left, if there are multiple solutions?

@hallvabo, oops haven't had coffee yet this morning. fixed it now

@FUZxxl, you have to put the multiple solutions on the same line, although for interest please submit the alternative version too if the requirement makes a large difference in your language

+1 when I get more votes :-)

How strict is the output format? Are the spaces needed? Are the left-hand numbers needed?

@J B, Just the (padding) leading spaces are optional. Extra trailing spaces would be ok too. The spaces around the = and after the , are required

@Joey, fixed that. base and exponent are > 1

May we return a list of strings?

Ruby 1.9, 112 111 99 characters
4097.times{|x|s=[]
2.upto(64){|a|2.upto(12){|b|a**b==x&&s<<[a,b]*?^}}
puts [x,s*", "]*" = "if s[0]}

This takes about 0.8 seconds to complete on my system. A faster solution is 111 characters long:
h={};(2..64).map{|a|(2..12).map{|b|a**b<4097&&(h[a**b]||=[])<<[a,b]*?^}}
puts h.sort.map{|a,b|[a,b*", "]*" = "}

Python, 113

R=range
for k in R(4097):
 v=', '.join(`i`+'^'+`j`for i in R(2,65)for j in R(2,13)if i**j==k)
 if v:print k,'=',v

This takes a few seconds to complete.
A faster (148 chars) version, using a dictionary to avoid the outermost loop, runs in ~ 0.01 sec:

R=range(2,65)
p={}
for i in R:
 for j in R:
    if i**j<4097:p[i**j]=p.get(i**j,[])+[`i`+'^'+`j`]
for k,v in sorted(p.items()):print k,'=',', '.join(v)

I'm pretty sure the equals sign is required for the output, though that shouldn't change the code size by much.

Whops, I accidentally removed it when I got rid of the (optional) leading whitespace. Fixed it!

Windows PowerShell, 102
With help by Ventero for the initial code.
$OFS=', '
4..4KB|%{$x=$_
if($s=2..64|%{$a=$_
2..12|?{[math]::pow($a,$_)-eq$x}|%{"$a^$_"}}){"$x = $s"}}

Interactive J, 118 101 98
3 :0"0 i.4097
if.#l=.":2j2+63(<.@%~j.|)I.y=,^/~2+i.63
do.echo(":y),' = ',l rplc j`^,' ';', 'end.
)

(last newline unneeded)
Still a lot of code for the presentation...
Note: in theory changing 63 and 63 to y and y saves 2 more bytes but that version uses extreme amount of memory.
Edited by randomra.

Using [space]j[backtick]^,' ';', ' instead of  'j';'^';' ';', ' saves 3 bytes. (Given up formatting it...)

@randomra You've got edit rights; please go ahead! (I can't find a box with J to verify with my current setup, and I'm in kind of in a hurry). This would make J the best of the show, it would be a pity not to show it off! :-)

Bash, 138 chars
i=2;j=1
f(){((v>4096))&&((j=1,++i))
a[$v]+="$i^$j, "
((v=i**++j,i<65))&&f
}
f
f(){
echo $j = ${a[$j]}
((j++<v))&&f
}
f|sed '/=$/d;s/.$//'

Edits

(169 : 155) 2 for for a while.
(155 : 148) Append with +=
(148 : 147) output with while, reusing j
(147 : 142) use sed to remove empty lines
(142 : 137) put v in (()), use v for 4096 (last value)
(137 : 134) remove sed quotes, join (()) expressions
(134 : 132) replace loops with recursive functions
(132 : 142) forgot the comma , :(
(142 : 138) tired of updates :p

PHP, 138 characters - Output
<?for($b=1;++$b<65;)for($e=1;++$e<13;)if(4097>$f=pow($b,$e))$p[$f][]="$b^$e";ksort($p);foreach($p as$n=>$c)echo"$n = ".join($c,", ")."\n";

Ungolfed
<?php

// Array of combinations

$powers = array();

// Loop through every base from 2 to 64, as 64 is the highest you can go

for($base = 2; $base < 65; $base++){

    // Loop through all powers from 2 to 12, as 12 is the maximum

    for($power = 2; $power < 13; $power++){

        // Calculate the power

        $end = pow($base, $power);

        // Kill the loop if the result is too high

        if($end > 4096){
            break;
        }

        // Add the combination if the result is within limits

        $powers[$end][] = $base."^".$power;
    }
}

// Sort the powers by the total amount

ksort($powers);

// Output the powers in the correct format

foreach($powers as $number => $combinations){
    echo $number." = ".implode($combinations, ", ")."\n";
}

Python, 127 chars
F={}
for i in range(693):a,b=i/11+2,i%11+2;F[a**b]=F.get(a**b,'')+', %d^%d'%(a,b)
for k in sorted(F)[:81]:print k,'=',F[k][2:]

Mathematica, 152 byte
Print/@Cases[Range@4096,n_/;(2<=##&&##==##&)@@(f=#2&@@@FactorInteger@#&)@n:>{n,Row[{n^(1/#),#}~Row~"^"&/@Reverse@Rest@Divisors@#,", "]&@@f@n}~Row~" = "]

This got embarrassingly long. Something like 25 characters are spent on output formatting. The actual code is fairly simple: filter those numbers where all exponents in the prime factorisation are equal. Then, for each of those produce one result for each divisor of the exponent (excluding 1, including itself).

OCaml + Batteries, 220 206 158 156 characters
Taking a hint from the best-scored solutions:
Printf.(iter(fun x->match
String.join", "[?List:sprintf"%d^%d"b e|b<-2--64;e<-2--12;float
x=float b**float e?]with""->()|s->printf"%5d = %s\n"x s)(4--4096))

(Line endings at significative whitespace to keep lines short.) A faster but longer version that generates powers instead of testing them:
Printf.(List.(iter(fun l->printf"%5d = %s\n"(fst(hd l))(String.join", "(map
snd l)))(group(fun(x,_)(y,_)->x-y)[?List:truncate p,sprintf"%d^%d"b
e|b<-2--64;e<-2--12;p<-List:[float b**float e];p<=4096.?])))

JavaScript, 160
o={}
i=2
s=''
n=4097
for(k=4;k<n;k=++i*i)for(j=2;k<n;k*=i)
{a=i+'^'+j
if(o[k])o[k]+=', '+a
else o[k]=a
j++}for(i=0;i<n;i++)if(o[i])s+='\n'+i+' = '+o[i]
alert(s)

194
o={},i=2,s='',n=4096
for(k=4;k<=n;k=i*i){for(j=2;k<=n;k*=i){o[k]=o[k]||[]
o[k].push(i+'^'+j)
j++}i++}
for(i=0;i<n;i++){if(o[i]){s+='\n'+i+' = '
for(j in o[i])s+=(j==0?'':', ')+o[i][j]}}
alert(s)

Rolled back; please post golfing suggestions as comments, not edits.

C (589 bytes)
int pow(int a,int b){
   int res = 1;
   while(b>0){
    while(b%2 == 0){
        a *= a; b/=2;
    }
    b--;
    res = res*a;
}
return res;
}
char s[99],t[9];

int main(){
   int N,T,a,i,f,e,n;
  for(n = 2; n <= 1<<12; n++){
      strcpy(s,"");
      T = N = n;
      f = 0;
      int sqt = sqrt(N)+1;
      for(i = 2; i <= sqt; i++){
         for(e=0;0==N%i;e++,N/=i);
           for(a = i; e > 1;e = e%2?(e+1)/2:e/2)
              for(a=i;a<T;pow(a,e)==T?f++?0:printf("%d =",T),sprintf(t,", %d^%d",a,e),strcat(s,t):0,a*=i);
    }
    f?puts(s+1):0;
   }
   return 0;
 }

I didn't golfed also this approach is not the best one but yet fast enough to produce an exact 0s in ideone.

Haskell, 146 characters
c[a]=a
c(a:z)=a++", "++c z
n#[]=""
n#s=shows n$" = "++c s++"\n"
main=putStr$(\n->n#[shows x$'^':show y|x<-[2..64],y<-[2..12],x^y==n])=<<[4..4096]

Pyth, 39 bytes
jm++^Fhd" = "j", "jL\^d<.g^Fk^tS64 2 81

Try it online here.
jm++^Fhd" = "j", "jL\^d<.g^Fk^tS64 2 81
                               S64       [1-64]
                              t          Discard first element
                             ^     2     Cartesian product of the above with itself
                        .g               Group the pairs, as k, using:
                          ^Fk              [a,b] -> a^b
                       <             81  Take the first 81 results of the above (those where exponential <= 4096)
 m                                       Map the remaining groups, as d, using:
                  jL\^d                    Join each pair in d on "^"
             j", "                         Join on ", "
  +     " = "                              Prepend " = "
   +^Fhd                                   Prepend the result of the exponent of one of the pairs
j                                        Join the result of the above on newlines, implicit print

If the output format is flexible enough to remove the need for spaces, -5 bytes to replace " = " with \= and ", " with \,

Haskell, 131
p[]=return()
p((x,y,z):s)=do print$show x++" = "++show y++"^"++show z;p s
main=p [(x,y,z)|x<-[2..2^12],y<-[2..x],z<-[2..x],x==y^z]

powers that have the same value are supposed to be on the same line

JavaScript, 148 chars
s=''
for(i=2;i<4097;i++){q=''
for(a=2;a<65;a++)for(b=2;b<13;b++)if(Math.pow(a,b)==i)q+=a+'^'+b+', '
if(q)s+=i+' = '+q.slice(0,-2)+"\n"}alert(s)

JavaScript (ES6) 134 127
Edit revised, bugfixed and shortened
Edit 2After some research, I realized that this answer was invalid for chronological reasons. The question predates arrow functions by years.
All that said, the other JS answers are way too complicated

/* for TEST:redefine console.log */ console.log=x=>O.innerHTML+=x+'\n';

for(l=[],b=1;++b<65;)for(e=2,r=b;(r*=b)<4197;)(l[r]=l[r]||[]).push(b+'^'+e++);l.some(function(v,i){console.log(i+' = '+v.join(', '))})

If you don't care too much about '=' formatting, then you can reduce down to 121 bytes: for(l=[],b=1;++b<65;)for(e=2,r=b;(r*=b)<4197;)(l[r]=l[r]||[]).push(b+'^'+e++);l.map((v,i)=>console.log(i+'='+v.join`, `))

@molarmanful there are strict requirements about formatting

Oh well... at least change the v.join part. That can at least bring the byte count down to 123.

@molarmanful at time this challenge (and this answer!) were posted, template strings were not implemented in any browser: Firefox was the first - rel 34, dec first 2014 - then Chrome, march 2015. You cannot use a feature that was available 3 years after the question

Oh well... I did not know that. I just got into ES6 a week ago!

C 184
Should compile (with warnings) with any C compiler
char*l[5000],*t=l+4100,*u;
main(b,e,r)
{
  for(;++b<65;)
    for(e=2,r=b;(r*=b)<4100;l[r]=u)
      t+=1+sprintf(u=t,"%s, %d^%d",l[r]?l[r]:"",b,e++);
  for(r=1;++r<4097;)
    l[r]&&printf("%d =%s\n",r,l[r]+1);
}

Pyth, 55 chars
=Tr2 64V^2 12JYFZTFbTIqN^ZbaJj\^[Zb))))IJjk[Nd\=dj", "J

My first time using Pyth, so it can probably be improved. It's a brute force that checks up to 64^64, thus is quite slow. You can save time by only checking up to 64^12 but it would cost a byte.

05AB1E, 36 bytes
2žxŸãΣ`m}99£.γ`m}εн`m'=yε'^ý}„, ý)}»

I have the feeling this can be improved a bit by using a slightly different approach..
Try it online.
Explanation:
2žxŸ           # Create a list in the range [2,64]
    ã          # Create each possible pair by taking the cartesian product with itself
Σ`m}           # Sort these `a,b`-pairs by their result of `a ** b`
    99£        # Only leave the first 99 pairs
       .γ`m}   # And then group the `a,b`-pairs by their result of `a ** b`
ε              # Now map each list of pairs `y` to:
 н             #  Take the first pair of list `y`
  `m           #  Take the `a ** b` value
 '=           '#  Push character "=" to the stack
 yε            #  Inner map over the pairs of list `y`:
   '^ý        '#   Join each pair with a "^" delimiter
      }„, ý    #  After the inner map: join these strings with a ", " delimiter
 )             #  Wrap all values on the stack into a list
}»             # After the outer map: join every inner list by spaces,
               # and the outer list by newlines (and output the result implicitly)

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Greatest greatest common divisor
Find the greatest gcd of the numbers \$n^m + k\$ and \$(n+1)^m + k\$ for given m and k.
For example, for m=3, k=1 we have:

\$n = 1\$: \$\gcd(1^3 + 1, 2^3 + 1) = 1\$
\$n = 2\$: \$\gcd(2^3 + 1, 3^3 + 1) = 1\$

\$\vdots\$

\$n = 5\$: \$\gcd(5^3 + 1, 6^3 + 1) = 7\$ (max)

\$\vdots\$

\$n \to \infty\$

Input/Output
Input is L lines through file or stdin, EOF terminated. Each line contains two integers: m and k separated by a space.
Output is L integers separated by any pattern of whitespace characters (tabs, spaces, newlines etc).
Examples
Input
2 4
2 7
3 1
4 1
3 2
5 4
10 5

Output
17
29
7
17
109
810001
3282561

Update
I can't find a proof that the solution is bounded for all n given some m and k, so you only have to find the GGCD for \$n < 10,000,000\$.

For m=5, k=4 value is >= 810001.

@Ante: Interesting! Are you sure? Do you know for what n is 810001?

n=329529. Are you sure that max(gcd(n,n+1) of series) is good defined? I can't find a proof or good rezone for that, except very much regularity in gcd(n,n+1) series.

Please clarify spec: how is n arrived at?

@mckenzie: brute force, iterating n to few millions and checking gcd().

Is n an integer? Is n >= 0?

@trinithis: gcd is by definition about non-zero integers, unless specified otherwise. Also, there is no point in taking n < 0 but feel free to do so if that shortens your code.

Update:
GGCD for given m and k is good defined.
This is table of GGCD tested for n up to 500000.
m/k      1       2       3       4       5       6       7       8       9      10
2        5       9      13      17      21      25      29      33      37      41
3        7     109      61     433     169     973     331    1729     547    2701
4       17      33      49      65      81      97     113     129     145    2093
5      341   52501  258751  810001       1  131371       1       1  501311 2846591
6       65     129     193     257   21507     385     449   22059     577     641
7     3683  235747       1       1      71  438299  940507   33461     757  110503
8     4369     513     769   13325    1281  149089  202609    2049  975937  617201
9   359233  232537  202927  470983  123019  708589  241117 5601589  398581   19783
10   62525  514299  183757  807517 1094187 16856405  97477    8193  377897 25919971

For m==2 or 4 it looks quite good :-)
It seems that if p_in_i is gcd for some n, where p_i is a prime, than every combination of products of p_i's with exponents <= n_i is also gcd for some n. E.g. for m=8,k=2, 3^3 and 19 are gcd of type p_in_i, also 57, 171 and 513 are gcd's.
Some theory background: If g = gcd(n) > 1 for some n, and d > 1 and d divide g (it can be d=g) than d divide gcd(n±d). It is easy to prove. That means:

If you find some g = gcd(n) > 1 for some n, than gcd(n±d) > 1. So, it is enough to jump for found prime number of steps while iterating n.
If prime p divide some gcd() than there is n <= p where p divide gcd(n). Prime p will 'appear' in gcd(n) for some n <= p.

These properties can speed up search, but still there is a question is GGCD good defined.

Except m=4,k=10 - that one is very interesting and breaks the pattern (2093).  Makes one wonder if you made n go higher you might find even higher numbers for m=4, k<10.

And m=7, k=9 has GGCD of at least 9846271 (see n=9790012).

@mellamokb: maybe it doesn't break a pattern, 161 is gcd() for n = 241. For m=4,k=10 there is no other gcd till n=10^7.

@Howard: Now I checked also till n=10^7:-) Since 757 and 9846271 are both prime, than 757*9846271=7453627147 is also gcd() for some large n.

@Ante: I was commenting about the fact that your table above has 2093 as the entry for m=4, k=10... or am I misreading the table??

@mellamokb: it has 2093, which is GGCD for n<=500000. 161 is smaller gcd, which should be expected extension of GGCDs for k<10, which are k*16+1.

@Ante: Gotcha, we're on the same page now.  I was meaning a pattern on GGCD, not patterns on possible gcd's that appear in the list.  So it's quite possible for an n>500000, perhaps there's a higher gcd for, say, m=4, k=3, which was my point.  No way to know unless the theory behind the patterns can be made more thorough and conclusive I guess :)

@Ante yes of course (it is for n=6400019891).

Ruby - 84 81 80 79 chars
Passes all test cases, not sure if it can handle larger numbers.
$<.map{|l|m,k=l.split.map &:to_i;p (1..$$).map{|n|(n**m+k).gcd (n+1)**m+k}.max}

Test
D:\tmp>ruby cg_gcd.rb < cg_gcd.in
17
29
7
17
109
3361

What happens if $$ becomes small? You cannot guarantee any value for it.

Sage, 92
for l in sys.stdin.readlines():m,k=l.split();print max(gcd(n^m+k,(n+1)^m+k)for n in[1..1e7])

Jelly, 9 bytes
*@Ɱȷ7+gƝṀ

Try it online!
This times out on TIO no matter the input due to the Ɱȷ7 which iterates over the range \$1, 2, ..., 10^7\$. By reducing the 7 to a smaller value, we can get TIO to actually output some results (obviously it gets it wrong for inputs where \$n > 10^5\$): Try it online!
Not exactly spec-conforming, but given the age I didn't see much issue with that. Takes input in the form of command line arguments. \$m\$ first, then \$k\$
How it works
*@Ɱȷ7+gƝṀ - Main link. Takes m as a left argument and k on the right
   ȷ7     - 10000000
  Ɱ       - Over each n between 1 and 10000000:
*@        -   Calculate n^m
     +    -   Add k
       Ɲ  - Over each neighbouring pair in the list (i.e. n^m+k and (n+1)^m+k):
      g   -   Calculate their GCD
        Ṁ - Output the maximum

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Solve 2-SAT (boolean satisfiability)
The general SAT (boolean satisfiability) problem is NP-complete.  But 2-SAT, where each clause has only 2 variables, is in P.  Write a solver for 2-SAT.
Input:
A 2-SAT instance, encoded in CNF as follows.  The first line contains V, the number of boolean variables and N, the number of clauses.  Then N lines follow, each with 2 nonzero integers representing the literals of a clause.  Positive integers represent the given boolean variable and negative integers represent the variable's negation.
Example 1
input
4 5
1 2
2 3
3 4
-1 -3
-2 -4

which encodes the formula (x1 or x2) and (x2 or x3) and (x3 or x4) and (not x1 or not x3) and (not x2 or not x4).
The only setting of the 4 variables that makes the whole formula true is x1=false, x2=true, x3=true, x4=false, so your program should output the single line
output
0 1 1 0

representing the truth values of the V variables (in order from x1 to xV).  If there are multiple solutions, you may output any nonempty subset of them, one per line.  If there is no solution, you must output UNSOLVABLE.
Example 2
input
2 4
1 2
-1 2
-2 1
-1 -2

output
UNSOLVABLE

Example 3
input
2 4
1 2
-1 2
2 -1
-1 -2

output
0 1

Example 4
input
8 12
1 4
-2 5
3 7
2 -5
-8 -2
3 -1
4 -3
5 -4
-3 -7
6 7
1 7
-7 -1

output
1 1 1 1 1 1 0 0
0 1 0 1 1 0 1 0
0 1 0 1 1 1 1 0

(or any nonempty subset of those 3 lines)
Your program must handle all N,V < 100 in a reasonable time.  Try this example to make sure your program can handle a big instance.  Smallest program wins.

You mention that 2-SAT is in P, but not that it is a requirement that the solution must run in polynomial time ;-)

@Timwi: No, but it has to handle V=99 in a reasonable time...

Haskell, 278 characters
(∈)=elem
r v[][]=[(>>=(++" ").show.fromEnum.(∈v))]
r v[]c@(a:b:_)=r(a:v)c[]++r(-a:v)c[]++[const"UNSOLVABLE"]
r v(a:b:c)d|a∈v||b∈v=r v c d|(-a)∈v=i b|(-b)∈v=i a|1<3=r v c(a:b:d)where i w|(-w)∈v=[]|1<3=r(w:v)(c++d)[]
t(n:_:c)=(r[][]c!!0)[1..n]++"\n"
main=interact$t.map read.words

Not brute force. Runs in polynomial time. Solves the hard problem (60 variables, 99 clauses) quickly:
> time (runhaskell 1933-2Sat.hs < 1933-hard2sat.txt)
1 1 1 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1 1 0

real 0m0.593s
user 0m0.502s
sys  0m0.074s

And actually, most of that time is spent compiling the code!
Full source file, with test cases and quick-check tests available.
Ungolf'd:
-- | A variable or its negation
-- Note that applying unary negation (-) to a term inverts it.
type Term = Int

-- | A set of terms taken to be true.
-- Should only contain  a variable or its negation, never both.
type TruthAssignment = [Term]

-- | Special value indicating that no consistent truth assignment is possible.
unsolvable :: TruthAssignment
unsolvable = [0]

-- | Clauses are a list of terms, taken in pairs.
-- Each pair is a disjunction (or), the list as a whole the conjuction (and)
-- of the pairs.
type Clauses = [Term]

-- | Test to see if a term is in an assignment
(∈) :: Term -> TruthAssignment -> Bool
a∈v = a `elem` v;

-- | Satisfy a set of clauses, from a starting assignment.
-- Returns a non-exhaustive list of possible assignments, followed by
-- unsolvable. If unsolvable is first, there is no possible assignment.
satisfy :: TruthAssignment -> Clauses -> [TruthAssignment]
satisfy v c@(a:b:_) = reduce (a:v) c ++ reduce (-a:v) c ++ [unsolvable]
  -- pick a term from the first clause, either it or its negation must be true;
  -- if neither produces a viable result, then the clauses are unsolvable
satisfy v [] = [v]
  -- if there are no clauses, then the starting assignment is a solution!

-- | Reduce a set of clauses, given a starting assignment, then solve that
reduce :: TruthAssignment -> Clauses -> [TruthAssignment]
reduce v c = reduce' v c []
  where
    reduce' v (a:b:c) d
        | a∈v || b∈v = reduce' v c d
            -- if the clause is already satisfied, then just drop it
        | (-a)∈v = imply b
        | (-b)∈v = imply a
            -- if either term is not true, the other term must be true
        | otherwise = reduce' v c (a:b:d)
            -- this clause is still undetermined, save it for later
        where
          imply w
            | (-w)∈v = []  -- if w is also false, there is no possible solution
            | otherwise = reduce (w:v) (c++d)
                -- otherwise, set w true, and reduce again
    reduce' v [] d = satisfy v d
        -- once all caluses have been reduced, satisfy the remaining

-- | Format a solution. Terms not assigned are choosen to be false
format :: Int -> TruthAssignment -> String
format n v
    | v == unsolvable = "UNSOLVABLE"
    | otherwise = unwords . map (bit.(∈v)) $ [1..n]
  where
    bit False = "0"
    bit True = "1"

main = interact $ run . map read . words
  where
    run (n:_:c) = (format n $ head $ satisfy [] c) ++ "\n"
        -- first number of input is number of variables
        -- second number of input is number of claues, ignored
        -- remaining numbers are the clauses, taken two at a time

In the golf'd version, satisfy and format have been rolled into reduce, though in order to avoid passing n, reduce returns a function from a list of variables ([1..n]) to the string result.

Edit: (330 -> 323) made s an operator, better handling of the newline
Edit: (323 -> 313) first element from a lazy list of results is smaller than a custom short-circuit operator; renamed main solver function 'cause I like using ∮ as an operator!
Edit: (313 -> 296) keep clauses as a single list, not a list of lists; process it two elements at a time
Edit: (296 -> 291) merged the two mutually recursive functions; it was cheaper to inline ★ so test now renamed ∈
Edit: (291 -> 278) inlined output formatting into results generation

J, 119 103
echo'UNSOLVABLE'"_`(#&c)@.(*@+/)(3 :'*./+./"1(*>:*}.i)=y{~"1 0<:|}.i')"1 c=:#:i.2^{.,i=:0&".;._2(1!:1)3

Passes all test cases. No noticeable runtime.
Brute force. Passes test cases below, oh, N=20 or 30. Not sure.
Tested via completely brain-dead test script (By visual inspection)

Edit: Eliminated (n#2) and thus n=:, as well as eliminating some rank parens (thanks, isawdrones). Tacit->explicit and dyadic->monadic, eliminating a few more characters each. }.}. to }.,.
Edit: Whoops. Not only is this a non-solution for large N, but i. 2^99x -> "domain error" to add insult to stupidity.
Here's the ungolfed original version and brief explanation.
input=:0&".;._2(1!:1)3
n =:{.{.input
clauses=:}.input
cases=:(n#2)#:i.2^n
results =: clauses ([:*./[:+./"1*@>:@*@[=<:@|@[{"(0,1)])"(_,1) cases
echo ('UNSOLVABLE'"_)`(#&cases) @.(*@+/) results

input=:0&".;._2(1!:1)3 cuts input on newlines and parses numbers on each line (accumulating the results into input).
n is assigned to n, clause matrix assigned to clauses (don't need the clause count)
cases is 0..2n-1  converted to binary digits (all test cases)
(Long tacit function)"(_,1) is applied to each case in cases with all of clauses.
<:@|@[{"(0,1)] gets a matrix of the operands of the clauses (by taking abs(op number) - 1 and dereferencing from case, which is an array)
*@>:@*@[ gets clause-shaped array of 'not not' bits (0 for not) via abuse of signum.
= applies the not bits to the operands.
[:*./[:+./"1 applies +. (and) across the rows of the resulting matrix, and *. (or) across the result of that.
All of those results end up as a binary array of 'answers' for each case.
*@+/ applied to results gives a 0 if there are results and 1 if there are none.
('UNSOLVABLE'"_) `(#&cases) @.(*@+/) results runs constant function giving 'UNSOLVABLE' if 0, and a copy of each 'solution' element of cases if 1.
echo magic-prints the result.

You could remove the parens around the rank arguments. "(_,1) to "_ 1. #: would work without the left argument.

@isawdrones: I think the traditional response would be to crush my spirit by producing an answer half as long. "Scream and leap", as the Kzin would say. Thanks, though, that eliminates 10-odd characters... I might get under 100 when I get back to it.

+1 for the nice and detailed explanation, very fascinating read!

Probably won't handle N=V=99 in a reasonable time.  Try the big example I just added.

K - 89
The same method as the J solution.
n:**c:.:'0:`;`0::[#b:t@&&/+|/''(0<'c)=/:(t:+2_vs!_2^n)@\:-1+_abs c:1_ c;5:b;"UNSOLVABLE"]

Nice, I didn't know there was a free K implementation.

Probably won't handle N=V=99 in a reasonable time.  Try the big example I just added.

OCaml + Batteries, 438 436 characters
Requires an OCaml Batteries Included top-level:
module L=List
let(%)=L.mem
let rec r v d c n=match d,c with[],[]->[String.join" "[?L:if x%v
then"1"else"0"|x<-1--n?]]|[],(x,_)::_->r(x::v)c[]n@r(-x::v)c[]n@["UNSOLVABLE"]|(x,y)::c,d->let(!)w=if-w%v
then[]else r(w::v)(c@d)[]n in if x%v||y%v then r v c d n else if-x%v then!y else if-y%v then!x else r v c((x,y)::d)n
let(v,_)::l=L.of_enum(IO.lines_of stdin|>map(fun s->Scanf.sscanf s"%d %d"(fun x y->x,y)))in print_endline(L.hd(r[][]l v))

I must confess, this is a direct translation of the Haskell solution. In my defense, that in turn is a direct coding of the algorithm presented here [PDF], with the mutual satisfy-eliminate recursion rolled into a single function. An unobfuscated version of the code, minus the use of Batteries, is:
let rec satisfy v c d = match c, d with
| (x, y) :: c, d ->
    let imply w = if List.mem (-w) v then raise Exit else satisfy (w :: v) (c @ d) [] in
    if List.mem x v || List.mem y v then satisfy v c d else
    if List.mem (-x) v then imply y else
    if List.mem (-y) v then imply x else
    satisfy v c ((x, y) :: d)
| [], [] -> v
| [], (x, _) :: _ -> try satisfy (x :: v) d [] with Exit -> satisfy (-x :: v) d []

let rec iota i =
    if i = 0 then [] else
    iota (i - 1) @ [i]

let () = Scanf.scanf "%d %d\n" (fun k n ->
    let l = ref [] in
    for i = 1 to n do
        Scanf.scanf "%d %d\n" (fun x y -> l := (x, y) :: !l)
    done;
    print_endline (try let v = satisfy [] [] !l in
    String.concat " " (List.map (fun x -> if List.mem x v then "1" else "0") (iota k))
    with Exit -> "UNSOLVABLE") )

(the iota k pun I hope you'll forgive).

Nice to see the OCaml version! It makes the start of a nice Rosetta Stone for functional programs. Now if we could get Scala and F# versions... -- As for the algorithm - I didn't see that PDF until you mentioned it here! I based my implementation off of the Wikipedia page's description of "Limited Backtracking".

Ruby, 253
n,v=gets.split;d=[];v.to_i.times{d<<(gets.split.map &:to_i)};n=n.to_i;r=[1,!1]*n;r.permutation(n){|x|y=x[0,n];x=[0]+y;puts y.map{|z|z||0}.join ' 'or exit if d.inject(1){|t,w|t and(w[0]<0?!x[-w[0]]:x[w[0]])||(w[1]<0?!x[-w[1]]:x[w[1]])}};puts 'UNSOLVABLE'

But it's slow :(
Pretty readable once expanded:
n,v=gets.split
d=[]
v.to_i.times{d<<(gets.split.map &:to_i)} # read data
n=n.to_i
r=[1,!1]*n # create an array of n trues and n falses
r.permutation(n){|x| # for each permutation of length n
    y=x[0,n]
    x=[0]+y
    puts y.map{|z| z||0}.join ' ' or exit if d.inject(1){|t,w| # evaluate the data (magic!)
        t and (w[0]<0 ? !x[-w[0]] : x[w[0]]) || (w[1]<0 ? !x[-w[1]] : x[w[1]])
    }
}
puts 'UNSOLVABLE'

Probably won't handle N=V=99 in a reasonable time.  Try the big example I just added.


text:
Fastest algorithm for decomposing a perfect power
A perfect power is a positive integer that's equal to one positive integer, to the power of another positive integer (e.g. ab is a perfect power). Note that trivial solutions (e.g. b=1) are excluded; specifically, the definition requires a ≥ 2 and b ≥ 2.
The task
Write a full program that takes any number of positive integers (separated by newlines) from standard input, and for each such input n, outputs all pairs of positive integers a, b (with a ≥ 2 and b ≥ 2) such that ab = n. Use the syntax a^b for these pairs. If multiple pairs of outputs are possible for a given input, print all of them, separated by spaces.
Note the victory condition below: the aim here is to optimize the program for speed, not size.
Example test cases
Input
 1745041
 1760929
 1771561
 1852321
 1868689
 1874161
 1885129
 1907161
 1953125
 113795717542678488615120001
 113795717546049421004105281

Output
 1745041 = 1321^2
 1760929 = 1327^2
 1771561 = 11^6 121^3 1331^2
 1852321 = 1361^2
 1868689 = 1367^2
 1874161 = 37^4 1369^2
 1885129 = 1373^2
 1907161 = 1381^2
 1953125 = 5^9 125^3
 113795717542678488615120001 = 10667507560001^2
 113795717546049421004105281 = 10667507560159^2

Clarifications

No more than 10000 inputs will be given on any single run of the program.
Your program, as written, should be able to handle numbers up to at least 30 digits long (meaning you will likely need to use bignum support). In order for the victory condition to be meaningful, though, the underlying algorithm behind your submission must be capable of working for arbitrary perfect powers, no matter how large they are.
Each input n will actually be a perfect power, i.e. there will always be at least one output corresponding to each given input.
There are no restrictions on programming language (as long as the language has sufficient power to complete the task).

Victory condition
The program with the fastest algorithm (i.e. with the fastest complexity) will be the winner. (Note that the fastest known perfect power decomposition algorithms can determine whether a number is a perfect power, and what the base and exponent are, without having to actually factorise the number; you may want to take this into account when choosing the algorithm for your problem.)
In the case that two programs are equally fast by this measure, the tiebreak will be to see which program runs faster in practice (on the stated testcases or, to avoid hard-coding, a similar set of test cases).

most efficient time complexity and fastest (for finite input) are not equivalent :)

It's kinda awkward competing for speed in such a fast task, since the program will end up I/O bound.

What if N has no non-trivial power representation?  Should we output "N =" or nothing?

@Keith Randall:I have updated the constraints.

downvoted because i/o timing is likely to be a large part of the time cost

Python, 207 chars
This takes O(log2 N) bigint ops.  O(log N) different exponents to try, and O(log N) binary search to find each base.
import sys
for N in map(int,sys.stdin.readlines()):
 p,s=2,''
 while 1<<p<=N:
  i,j=2,N
  while j>i+1:
   m=(i+j)/2
   if m**p>N:j=m
   else:i=m
  if i**p==N:s+=' %d^%d'%(i,p)
  p+=1
 if s:print N,'=',s[1:]

You know, you could ditch the golfing length variable names ;-)

@eBusiness, force of habit...

map(int, sys.stdin) should work fine

C - No bigints
My solution use a 64 bit float and a 64 bit integer in combination to produce the result without using slow bignumber arithmetic. First a possible set of values that fit the high-order bits are produced using floats, then the low order is checked using integers. Due to 64 bit floats having 53 bit mantissa the method will break for numbers around 106 bit in length, but the task was only for up to 100 bit numbers.
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "math.h"
#define i64 unsigned long long
#define i32 unsigned int
#define f64 double

int main(){
    char inp[31];
    while(1==scanf("%30s",inp)){
        printf("%s =",inp);

        f64 upper=strtod(inp,NULL);
        //i64 lower=strtoull(inp,NULL,10);
        //i64 lower=atoll(inp);
        //Neither library function produce input mod 2^64 like one would expect, fantabulous!
        i64 lower=0;
        i32 c=0;
        while(inp[c]){
            lower*=10;
            lower+=inp[c]-48;
            c++;
        }
        f64 a,b;
        i64 candidate;
        f64 offvalue;
        f64 offfactor;
        i32 powleft;
        i64 product;
        i64 currentpow;
        for(a=2;a<50;a++){ //Loop for finding large bases (>3).
            b=1.0/a;
            b=pow(upper,b);
            candidate=(i64)(b+.5);
            if(candidate<4){
                break;
            }
            offvalue=b-(f64)candidate;
            offfactor=fabs(offvalue/b);
            if(offfactor<(f64)1e-14){
                product=1;
                powleft=(i32)a;
                currentpow=candidate;
                while(powleft){ //Integer exponentation loop.
                    if(powleft&1){
                        product*=currentpow;
                    }
                    currentpow*=currentpow;
                    powleft=powleft>>1;
                }
                if(product==lower){
                    printf(" %I64u^%.0lf",candidate,a);
                }
            }
        }
        for(candidate=3;candidate>1;candidate--){ //Loop for finding small bases (<4), 2 cycles of this saves 50 cycles of the previous loop.
            b=log(upper)/log(candidate);
            a=round(b);
            offfactor=fabs(a-b);
            if((offfactor<(f64)1e-14) && (a>1)){
                product=1;
                powleft=(i32)a;
                currentpow=candidate;
                while(powleft){ //Integer exponentation loop.
                    if(powleft&1){
                        product*=currentpow;
                    }
                    currentpow*=currentpow;
                    powleft=powleft>>1;
                }
                if(product==lower){
                    printf(" %I64u^%.0lf",candidate,a);
                }
            }
        }
        printf("\n");
        if(inp[0]==113){ //My keyboard lacks an EOF character, so q will have to do.
            return 0;
        }
    }
    return 0;
}

As for runtime, ideone produce a clean 0 http://www.ideone.com/HJl2f this should be a pretty superior method, but any attempt to verify this will drown in I/O.

Ruby
Non-golfed, not-really-optimized solution. I hope I didn't mess up my math.
Roots are calculated first using core sqrt and cbrt methods, then using dumb approximation (binary search).
On my PC, 10000 long random inputs (not necessarily actually having non-trivial representations) take ~30 seconds (see the bench method).
def root start, exp, startapprox=nil
    if exp==1
        return start
    elsif exp==2
        return Math.sqrt(start).round
    elsif exp==3 and Math.respond_to? :cbrt # 1.9 only
        return Math.cbrt(start).round
    else
        lower=0
        upper=startapprox||Math.sqrt(start).ceil

        until upper-lower<=1
            res=(lower+upper)/2

            if res**exp<start
                lower=res+1
            else
                upper=res
            end
        end

        distlow=(start - lower**exp).abs
        distupp=(start - upper**exp).abs

        if distlow<distupp
            return lower
        else
            return upper
        end
    end
end

def powers number
    ret=[]
    skip=[]

    maxexp=(Math.log2 number).floor
    prev=nil

    2.upto(maxexp) do |exp|
        next if skip[exp]

        rt=root number, exp, prev
        if number==rt**exp
            ret<<"#{rt}^#{exp}"
        else
            (exp..maxexp).step(exp){|i| skip[i]=true} # if it's not 2nd power, it cant be 4th power etc
        end

        prev=rt
    end

    "#{number} = #{ret.reverse.join ' '}"
end

def bench n=10
    require 'benchmark'

    Array.new(n){Benchmark.realtime{powers rand 1e30}}.inject(:+)
end

# read input, output powers
if __FILE__==$0
    while (a=gets.strip).length>0
        puts powers a.to_i
    end
end

Can't you just calculate roots as a**(1/b)?

@eBusiness Whoa, true. I've never though of it. It reduces execution time to ~10 seconds.

C++, not sure if it's correct
#include <iostream>
#include<iomanip>
#include <cstdio>
#include <cmath>
using namespace std;
int main() {
long double x;
char s[120];
ios::sync_with_stdio(false);
//cout << setprecision(20);
while (cin >> s) {
    cout << s << " =";
    //sscanf (s, "%Lf", &x);
    x = 0;
    for (char*p=s; *p; p++) {
        x = 10*x + (*p-48);
    }
    for (int i=2; ; i++) {
        long double tmp = pow(x, 1./i);
        if (tmp<1.98) break;
        long long inty = tmp + 0.5;
        tmp = powl(inty, i) - x;
        //cout << "[" << i << ' ' << inty << ' ' << tmp << "]\n";
        if (abs(tmp * 1e19) < x)
            cout << ' ' << inty << '^' << i;
    }
    cout << '\n';
}
}

If Each input n will actually be a perfect power, numbers may needn't be not so accurate/precise. Here my long double is TBYTE type, though sizeof(x) is 12

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Code-Golf: Lattice Points inside a Circle
The following picture shows the problem:

Write a function that, given an integer as the circle radius, calculates the number of lattice points inside the centered circle (including the boundary).
The image shows:
f[1] = 5  (blue points)
f[2] = 13 (blue + red points)

other values for your checking/debugging:
f[3]    = 29
f[10]   = 317
f[1000] = 3,141,549
f[2000] = 12,566,345

Should have a reasonable performance. Let's say less than a minute for f[1000].
Shortest code wins. Usual Code-Golf rules apply.
Please post the calculation and timing of f[1001] as an example.

https://oeis.org/A328

Triangular version.

J, 21 19 18
+/@,@(>:|@j./~@i:)

Builds complexes from -x-xj to x+xj and takes magnitude.
Edit: With >:
Edit 2: With hook and monadic ~. Runs a few times slower for some reason, but still 10-ish seconds for f(1000).

Oh hey, I didn't know about i:, I am so stealing that, thanks!

@J B: Yeah, well... I'm stealing >:. derp

I wish I understood caps well enough to steal those too O:-)

This answer is depressingly short (to someone who's never bothered to learn a short and/or golfing lang) >:. But hey, that's a cool answer! :)

J, 27 21
3 :'+/,y>:%:+/~*:i:y'

Very brutal: computes sqrt(x²+y²) over the [-n,n] range and counts items ≤n.  Still very acceptable times for 1000.
Edit: i:y is quite a bit shorter than y-i.>:+:y.  Thanks Jesse Millikan!

Ha! That was the idea behind asking a decent performance! Just curious: What is the timing for 1000?

@belisarius: 0.86s.  On 10-year old hardware.  3.26s for 2000.

Ruby 1.9, 62 58 54 characters
f=->r{1+4*eval((0..r).map{|i|"%d"%(r*r-i*i)**0.5}*?+)}

Example:
f[1001]
=> 3147833

t=Time.now;f[1001];Time.now-t
=> 0.003361411

Python 55 Chars
f=lambda n:1+4*sum(int((n*n-i*i)**.5)for i in range(n))

f=lambda n:1+4*sum(int((n*n-i*i)**.5)for i in range(n)) is 17 characters shorter.

Haskell, 41 bytes
f n=1+4*sum[floor$sqrt$n*n-x*x|x<-[0..n]]

Counts points in the quadrant x>=0, y>0, multiplies by 4, adds 1 for the center point.

Uiua, 13 bytes
∧+1×4⌊√×⊃+-⇡.

Try it online!
Uses the formula on A057655 \$ 1+4\sum_{k=0}^{n}{\left\lfloor\sqrt{n^2-k^2}\right\rfloor} \$, and uses the fact that k=n part can be removed.
∧+1×4⌊√×⊃+-⇡.    input: integer n
            ⇡.    keep n and generate the range for k
       ×⊃+-      (n+k) * (n-k) for each k
      ⌊√          sqrt, floor
∧+1×4            multiply 4, sum, and add 1

Haskell, 44 bytes
f n|w<-[-n..n]=sum[1|x<-w,y<-w,x*x+y*y<=n*n]

I'm new to Haskell: How can you write w<-[-n..n] where (usually) there is a boolean value?

@flawr These are pattern guards, which succeed if a pattern is matched, but can be used in golfing as a shorter let. See this tip.

Thanks, I was not aware of this this thread!

Japt -x, 12 bytes
òUn)ï Ëx²§U²

Try it online!
Explanation:
òUn)            #Get the range [-input ... input]
    ï           #Get each pair of numbers in that range
      Ë         #For each pair:
       x        # Get the sum...
        ²       # Of the squares
         §      # Check if that sum is less than or equal to...
          U²    # The input squared
                #Output the number of pairs that passed the check

12 bytes

Python 2, 48 bytes
f=lambda n,i=0:i>n or(n*n-i*i)**.5//1*4+f(n,i+1)

Like fR0DDY's solution, but recursive, and returns a float. Returning an int is 51 bytes:
f=lambda n,i=0:i>n or 4*int((n*n-i*i)**.5)+f(n,i+1)

JavaScript (ES6), 80 bytes
n=>(a=[...Array(n+n+1)].map(_=>i--,i=n)).map(x=>a.map(y=>r+=x*x+y*y<=n*n),r=0)|r

Alternative version, also 80 bytes:
n=>[...Array(n+n+1)].map((_,x,a)=>a.map((_,y)=>r+=x*x+(y-=n)*y<=n*n,x-=n),r=0)|r

ES7 version, also 80 bytes:
n=>[...Array(n+n+1)].map((_,x,a)=>a.map((_,y)=>r+=(x-n)**2+(y-n)**2<=n*n),r=0)|r

PHP, 85 83 bytes
The code:
function f($n){for($x=$n;$x;$c+=$x,$y++)for(;$n*$n<$x*$x+$y*$y;$x--);return$c*4+1;}

Its outcome (check https://3v4l.org/bC0cY for multiple PHP versions):
f(1001)=3147833
time=0.000236 seconds.

The ungolfed code:
/**
 * Count all the points having x > 0, y >= 0 (a quarter of the circle)
 * then multiply by 4 and add the origin.
 *
 * Walk the lattice points in zig-zag starting at ($n,0) towards (0,$n), in the
 * neighbourhood of the circle. While outside the circle, go left.
 * Go one line up and repeat until $x == 0.
 * This way it checks about 2*$n points (i.e. its complexity is linear, O(n))
 *
 * @param int $n
 * @return int
 */
function countLatticePoints2($n)
{
    $count = 0;
    // Start on the topmost right point of the circle ($n,0), go towards the topmost point (0,$n)
    // Stop when reach it (but don't count it)
    for ($y = 0, $x = $n; $x > 0; $y ++) {
        // While outside the circle, go left;
        for (; $n * $n < $x * $x + $y * $y; $x --) {
            // Nothing here
        }
        // ($x,$y) is the rightmost lattice point on row $y that is inside the circle
        // There are exactly $x lattice points on the row $y that have x > 0
        $count += $x;
    }
    // Four quarters plus the center
    return 4 * $count + 1;
}

A naive implementation that checks $n*($n+1) points (and runs 1000 times slower but still computes f(1001) in less than 0.5 seconds) and the test suite (using the sample data provided in the question) can be found on github.

APL (Dyalog Extended), 14 bytes
{≢⍸⍵≥|⌾⍀⍨⍵…-⍵}

Try it online!
Despite lacking the i: (inclusive range from -n to n) builtin of J, APL Extended has shorter syntax in other areas.
{≢⍸⍵≥|⌾⍀⍨⍵…-⍵}            Monadic function taking an argument n.
           ⍵…-⍵             n, n-1, ..., -n
      ⌾⍀                   Make a table of complex numbers
                            (equivalent to ∘.{⍺+1J×⍵} in Dyalog APL)
         ⍨                  with both real and imaginary parts from that list.
      |                       Take their magnitudes.
    ⍵≥                        1 where a magnitude are is at most n, and 0 elsewhere.
 ⍸                           Get all indices of truthy values.
≢                            Find the length of the resulting list.

C (gcc), 60 bytes
r,a;f(x){for(a=r=x*x;a--;)r-=hypot(a%x+1,a/x)>x;x=4*r+1;}

Try it online!
Loops over the first quadrant, multiplies the result by 4 and adds one. Slightly less golfed
r,a;
f(x){
  for(a=r=x*x;a--;)
    r-=hypot(a%x+1,a/x)>x;
  x=4*r+1;
}

Scala, 55 bytes
Try it online!
n=>(0 until n).map(i=>Math.sqrt(n*n-i*i).toInt).sum*4+1

JavaScript (ES7), 42 bytes
f=(n,k=n)=>k--?((n*n-k*k)**.5<<2)+f(n,k):1

Try it online!

Clojure/ClojureScript, 85 chars
#(apply + 1(for[m[(inc %)]x(range 1 m)y(range m):when(<=(+(* x x)(* y y))(* % %))]4))

Brute forces the first quadrant, including the y axis but not the x axis.  Generates a 4 for every point, then adds them together with 1 for the origin.  Runs in under 2 seconds for input of 1000.
Abuses the hell out of for to define a variable and save a few characters.  Doing the same to create an alias for range doesn't save any characters (and makes it run significantly slower), and it seems unlikely that you're going to save anything by making a square function.

This is quite an old question, are you sure this answer would have worked at the time?

@muddyfish I didn't notice the age, just saw it near the top.  Clojure predates the question, but I don't know its history enough to know about language changes.

Pyke, 14 bytes
QFXQX-_,B)s}}h

Try it here!

Mathematica, 35 characters
f[n_]:=Sum[SquaresR[2,k],{k,0,n^2}]

Lifted from https://oeis.org/A000328
https://reference.wolfram.com/language/ref/SquaresR.html
SquaresR[2,k] is the number of ways to represent k as the sum of two squares, which is the same as the number of lattice points on a circle of radius k^2. Sum from k=0 to k=n^2 to find all the points on or inside a circle of radius n.

2~SquaresR~k~Sum~{k,0,#^2}& to make it shorter

Tcl, 111 bytes
lassign {1001 0 -1} r R x
while {[incr x]<$r} {set R [expr {$R+floor(sqrt($r*$r-$x*$x))}]}
puts [expr {4*$R+1}]

Simple discrete x loop over quadrant I, counting largest y using the Pythagorean Theorem at each step. Result is 4 times the sum plus one (for the center point).
The size of the program depends on the value of r. Replace {1001 0 -1} with "$argv 0 -1" and you can run it with any command-line argument value for r.
Computes f(1001) → 3147833.0 in about 1030 microseconds, AMD Sempron 130 2.6GHz 64-bit processor, Windows 7.
Obviously, the larger the radius, the closer the approximation to PI: f(10000001) runs in about 30 seconds producing a 15-digit value, which is about the precision of a IEEE double.

Stax, 11 bytes
ä÷²M╨⌐■╝^₧░

Run and debug it

Pascal, 128 B
This just walks the lattice grid and checks whether the distance to the origin is less than or equal to the radius.
type Z=integer;function f(r:Z):Z;var x,y,n:Z;begin
n:=0;for x:=-r to r do for y:=-r to r do n:=n+ord(sqrt(x*x+y*y)<=r);f:=n
end;

User time on a busy Linux x86‑64 machine for calculating f(1001) = 3147833: ca. 80 ms.
Calculate just the points in one quadrant to cut the time.

C (gcc), 116 bytes
a,x,y;c(r){for(x=-r;x<=r;x++)for(y=-r;y<=r;a+=x*x+y*y<=r*r,y++);return a;}main(r){scanf("%u",&r);printf("%d",c(r));}

How it works
This inefficient method draws a square around the circle then iterates through all lattice points \$(x,y)\$ within it and checking if \$x^2+y^2 \le r^2 \$.
Try it online!

Hello, I'd like to shorten my answer above by using this tio.run technique from this C example. Any tips to make it work so it results in fewer bytes? Thanks.

111 bytes

@ceilngcat Is there a way to make it even shorter? I've asked the question here. Thanks.

73 bytes

@ceilingcat Thanks for those saved bytes and the TIO example. Is there a way to remove that return statement? I think there's a way to resolve that using a code golf that returns the value such as x=a.

APL (Dyalog Unicode) (SBCS), 28 bytes
{1+4×⍵++/,(×⍨⍵)≥+/¨×⍨∘.,⍨⍳⍵}
{                          } dfn
                     ∘.,⍨⍳⍵  get cartesian square of 1..n
                   ×⍨        square each half of each pair
                +/¨          add each half of each pair
       +/,     ≥             count sums greater than
          (×⍨⍵)                  the input squared
 1+4×⍵+                      add the input, multiply by 4, and add 1

Finds the lattice points in one quadrant, then multiplies it by 4 and adds the points on the axes.
Try it online!

05AB1E, 9 bytes
(Ÿn¬sãO@O

Port of @KamilDrakari's Japt answer, so make sure to upvote that answer as well!
Try it online or verify all test cases. (Runs 1001 in about 3.5 seconds on TIO.)
Explanation:
(          # Negate the (implicit) input-integer
 Ÿ         # Push a list in the range [(implicit) input,-input]
  n        # Square each inner value
   ¬       # Push the first item (without popping the list), which is input²
    s      # Swap so the list is at the top again
     ã     # Cartesian power of 2 to get all possible pairs
      O    # Sum all those inner pairs together
       @   # Check for each whether the input² is >= this value
        O  # Sum to get the amount of truthy values
           # (which is output implicitly as result)

Try it online with a step-by-step output.

APL(NARS), 25 chars
{1+4×+/⌊√(⍵*2)-¨2*⍨¯1+⍳⍵}

test:
  f←{1+4×+/⌊√(⍵*2)-¨2*⍨¯1+⍳⍵}
  f 0
1
  f 1
5
  f 3
29
  f 10
317
  f 1000
3141549
  f 2000
12566345


text:
Find all Super Powers
A positive number is said to be super power when it is the power of at least two different positive integers. Write a program that lists all super powers in the interval [1, 264) (i.e. between 1 (inclusive) and 264 (exclusive)).
Sample Output
1
16
64
81
256
512
.
.
.
18443366605910179921
18444492376972984336
18445618199572250625

Constraints:

The program should not take more than 10 secs.
There are 67385 super powers below 264.
The shortest code wins.

The time part is a quite severe limitation on environment, many slow consoles will be out because they basically can't do 10k lines per second.

@eBusiness Keeping in mind your point, should 20 secs be enough?

I think it might just do it for my GolfScript, but I'd rather make it a minute.

@eBusiness: What if you output to file instead?

That helps, put me down to less than 3 seconds for the output. Now to see if I can do the actual task quick enough...

GolfScript 52 characters
64,4>{1.{16.?<}{;).2$?}/@.,1>{2$\%*}**!*\;~}%$.&{p}/

I golfed this pretty heavily, here is a compilation of midway solutions:
;64,4>{.,2>{\.@%}%{*}*!\;},{1.{16.?<}{;).2$?}/]2=}%[]*$0\{.@={}{.p}if}/;
;64,4>{.,2>{\.@%}%{*}*!\;},{1.{16.?<}{;).2$?}/]2=}%[]*$.&{p}/
;64,4>{.,2>{\.@%}%{*}*!\;},{1.{16.?<}{;).2$?}/]2=~}%$.&{p}/
;4.{64<}{;)..,1>{2$\%*}*!*}/0-\;{1.{16.?<}{;).2$?}/]2=~}%$.&{p}/
;64,4>{.,1>{2$\%*}*!*},{1.{16.?<}{;).2$?}/]2=~}%$.&{p}/
;64,4>{.,1>{2$\%*}*{1.{16.?<}{;).2$?}/~}or]2>~}%$.&{p}/
64,4>{.,1>{2$\%*}*!\1.{16.?<}{;).2$?}/\;\;*~}%$.&{p}/
64,4>{1.{16.?<}{;).2$?}/\;\.,1>{2$\%*}*!\;*~}%$.&{p}/
64,4>{1.{16.?<}{;).2$?}/@.,1>{2$\%*}**!*\;~}%$.&{p}/

GolfScript seems to have some problem with outputting large arrays, therefore I step through the result array using {p}/ rather than just inject the needed lineshifts using n*.
The first 5 versions work by first generating an array of nonprimes from 4 to 63 (code before {1.), then for each element of that list all N^nonprime less than 2^64 is calculated (1.{16.?<}{;).2$?}/). Finally the result is sorted, duplicates are removed and the result is output.
In the 6th version the 2 first functions are put in the same loop.
In the 7th version the N^nonprime array is generated no matter if the nonprime is actually a nonprime, the array is then thrown away if needed.
In the 8th and 9th version the order has been switched so the N^nonprime array is generated before nonprime status is asserted.
By the way, a^b where a>0, b>1 and b is nonprime is probably a more programming-friendly way of describing super powers.

Ruby, 97 93 characters
puts (r=2..32).map{|j|r.map{|i|(1..2**(64.0/j/i)).map{|a|a**(j*i)}}}.flatten.uniq.sort[0..-2]

I'm pretty sure this should be correct.
$ time ruby1.9 perfectpower.rb > out

real    0m0.199s
user    0m0.160s
sys     0m0.030s

$ wc -l out
67385 out

$ head -6 out
1
16
64
81
256
512

$ tail -3 out
18443366605910179921
18444492376972984336
18445618199572250625

Python, 107 chars
R=range
for x in sorted(set(i**(j*k)for i in R(65536)for j in R(2,32)for k in R(2,64/j)))[1:67386]:print x

Takes about 40 seconds on my machine, though.

Well, you do make a set of several million numbers, up to 1024 bit in length. May I suggest that you move for i in R to the other end of the for stack and give it a sensible limit like ceil(2^(64/j/k)+2)?