Most "compact" sequence such that there is at least one prime between a(n) and a(n+1)

[Hugo Pfoertner]

>I believe it has been proved that there is always a prime between n^3 
>and (n+1)^3.  So the cubes are a considerably more compact example.
>
>Franklin T. Adams-Watters

Legendre's conjecture says that already the squares will do the job.
http://www.research.att.com/~njas/sequences/A000290
http://www.research.att.com/~njas/sequences/A007491

The Mathworld article http://mathworld.wolfram.com/LegendresConjecture.html suggests that a(n)=floor(n^(42/23)) might be a near optimal example:

    1    3    7   12   18   26   34   44   55   67   79   93  108  123  140
  158  176  195  216  237  259  282  306  331  357  383  410  439  468  498
  528  560  592  626  660  694  730  767  804  842  881  920  961 1002 1044
 1087 1130 1175 1220 1266 1312 1360 1408 1457 1506 1557 1608 1660 1712 1766
 1820 1875 1930 1987 2044 2102 2160 2219 2279 2340 2401 2464 2526 2590 2654
 2719 2785 2851 2918 2986 3055 3124 3194 3265 3336 3408 3481 3554 3628 3703
 3779 3855 3932 4009 4087 4166 4246 4326 4407 4489 4571 4654 4738 4822 4907
 4993 5079 5166 5254 5342 5431 5521 5611 5702 5794 5886 5979 6073 6167 6262
 6358 6454 6551 6649 6747 6846 6945 7046 7146 7248 7350 7453 7556 7660 7765
 7870 7976 8083 8190 8298 8407 8516 8626 8736 8848 8959 9072 9185 9298 9413
 9527 9643 9759 9876 9993

Even when the boundary points of the intervals are excluded, there seems to be at least one prime inside every interval:
           a           b     #of primes p with a<=p<=b
           2           2           1
           4           6           1
           8          11           1
          13          17           2
          19          25           2
          27          33           2
          35          43           3
          45          54           2
          56          66           2
          68          78           2
          80          92           2
          94         107           4
 

Hugo Pfoertner