Return to Answer

in both cases (n=1 and n>1), you will get a non empty first page link and the the output of paginate_links() will be something like:

in both cases (n=1 and n>1) and you have a non empty first page link with the output of paginate_links():

'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) ),
'format' => '/page/%#%',

in both cases (n=1 and n>1). Therefore you will get a non empty first page link and the the output of paginate_links() will be something like:

<ul class='page-numbers'>
    <li><a class="prev page-numbers" href="http://example.com/page/2/">&laquo; Previous</a></li>
    <li><a class='page-numbers' href='http://example.com/page/1/'>1</a></li>
    <li><a class='page-numbers' href='http://example.com/page/2/'>2</a></li>
    <li><span class='page-numbers current'>3</span></li>
    <li><a class='page-numbers' href='http://example.com/page/4/'>4</a></li>
    <li><a class='page-numbers' href='http://example.com/page/5/'>5</a></li>
    <li><a class='page-numbers' href='http://example.com/page/6/'>6</a></li>
    <li><a class="next page-numbers" href="http://example.com/page/4/">Next &raquo;</a></li>
</ul>

It should also work if you use:

'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) ),
'format' => '/page/%#%',

To have a non empty first page link it looks like $format can be any string as long as $base doesn't include the string "%_%". If you don't use permalinks, then the example in (#) will also give you non empty first page link.

'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) ),
'format' => '?paged=%#%',

in both cases (n=1 and n>1), you will get a non empty first page link and the the output of paginate_links() will be something like:

<ul class='page-numbers'>
    <li><a class="prev page-numbers" href="http://example.com/page/2/">&laquo; Previous</a></li>
    <li><a class='page-numbers' href='http://example.com/page/1/'>1</a></li>
    <li><a class='page-numbers' href='http://example.com/page/2/'>2</a></li>
    <li><span class='page-numbers current'>3</span></li>
    <li><a class='page-numbers' href='http://example.com/page/4/'>4</a></li>
    <li><a class='page-numbers' href='http://example.com/page/5/'>5</a></li>
    <li><a class='page-numbers' href='http://example.com/page/6/'>6</a></li>
    <li><a class="next page-numbers" href="http://example.com/page/4/">Next &raquo;</a></li>
</ul>

To have a non empty first page link it looks like $format can be any string as long as $base doesn't include the string "%_%", i.e. these should work fine:

'format' => '?paged=%#%',
'format' => 'page/%#%',
'format' => 'asdfasdfasdfasdfasdf',

If you don't use permalinks, then the example in (#) will also give you non empty first page link since

$link = str_replace('%_%', 1 == $n ? '' : "?paged=%#%", "http://example.com/?paged=%#%");   

with replacements.

I took a look at the paginate_links() source code (v3.5.1) and there is this line (#)

To have a non empty first page link it looks like $format can be any string as long as $base doesn't include the string "%_%".

Short answer:

Try

'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) ),
'format' => '/page/%#%',

Long answer:

I took a look at the paginate_links() source code (v3.5.1) and there is this line (#)

It should also work if you use:

'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) ),
'format' => '/page/%#%',

To have a non empty first page link it looks like $format can be any string as long as $base doesn't include the string "%_%". If you don't use permalinks, then the example in (#) will also give you non empty first page link.