How many $k$ satisfy the equation $(p \cdot k)^2 \equiv 0 \pmod{p^n}$ where $k < p^n$ and $p$ is prime How many $k$ satisfy the equation $(p \cdot k)^2 \equiv 0 \pmod{p^n}$ where $k < p^n$ and $p$ is prime?
I attach very simple code:
#include <stdio.h>
#include <math.h>

unsigned long long int ipow( unsigned long long int base, unsigned long long int exp )
{
    unsigned long long int result = 1ULL;

    while( exp )
    {
        if ( exp & 1 )
        {
            result *= (unsigned long long int)base;
        }
        exp >>= 1;
        base *= base;
    }

    return result;
}


int main()
{
    long long int p = 3;

    long int j;
    for(j=2; j < 25; j++)
    {

        long long int limit = ipow(p, j);

        long long int count = 0;

        long long int i;
        for(i=0; i < limit; i+=p)
        {
            if( (i*i) % limit == 0 )
                count++;    
        }

        printf("n=%ld count=%lld\n", j, count);

    }

    return 0;
}

For $p=3$ it return:
n=2 count=3
n=3 count=3 
n=4 count=9 
n=5 count=9 
n=6 count=27 
n=7 count=27 
n=8 count=81 
n=9 count=81 
n=10 count=243 
n=11 count=243
n=12 count=729
n=13 count=729
n=14 count=2187
n=15 count=2187
n=16 count=6561
n=17 count=6561
n=18 count=19683
n=19 count=19683
n=20 count=51432
n=21 count=17144
n=22 count=17146

I am interested in the case for very large $n$ (and $p$).
 A: I believe your program is wrong, for example for $p=3$, $n=3$ and   $k<3^3$
$$3^3 \mid (3 \cdot 3 \cdot 1)^2$$
$$3^3 \mid (3 \cdot 3 \cdot 2)^2$$
$$...$$
$$3^3 \mid (3 \cdot 3 \cdot 8)^2$$
where $k=3\cdot 8 < 3^3$, so there are $8$ cases, not $3$.

Generally (using Euclid lemma)
$$p^n \mid p^2 k^2 \Rightarrow p^{n-2} \mid k^2$$
from $p \mid k^2 \Rightarrow p^2 \mid k^2$ we have


*

*if $n-2$ - even then $p^{n-2}\mid k^2$

*if $n-2$ - odd then $p^{n-2+1}\mid k^2$


which is equivalent to $p^{2 \left \lfloor \frac{n-2+1}{2} \right \rfloor }\mid k^2$. As a result
$$p^{2 \left \lfloor \frac{n-2+1}{2} \right \rfloor } \leq k_1^2=p^{2 \left \lfloor \frac{n-2+1}{2} \right \rfloor } \cdot 1^2 < p^{2n}$$
$$p^{2 \left \lfloor \frac{n-2+1}{2} \right \rfloor } \leq k_2^2=p^{2 \left \lfloor \frac{n-2+1}{2} \right \rfloor } \cdot 2^2 < p^{2n}$$
$$...$$
$$p^{2 \left \lfloor \frac{n-2+1}{2} \right \rfloor } \leq k_q^2=p^{2 \left \lfloor \frac{n-2+1}{2} \right \rfloor } \cdot q^2 < p^{2n}$$
or
$$1 \leq 1^2 < p^{2n - 2 \left \lfloor \frac{n-2+1}{2} \right \rfloor }$$
$$1 \leq 2^2 < p^{2n - 2 \left \lfloor \frac{n-2+1}{2} \right \rfloor }$$
$$...$$
$$1 \leq q^2 < p^{2n - 2 \left \lfloor \frac{n-2+1}{2} \right \rfloor }$$
and there are 
$$p^{n - \left \lfloor \frac{n-2+1}{2} \right \rfloor }-1$$ such $k$'s.
A: First, your code needs modification to calculate what you need:
        if( (i*i) % limit == 0 )

this should be 
        if( (p*p*i*i) % limit == 0 )

(In the following I consider when $n>2$ since when $n=2$ or 1, all $k$ satisfy the condition.)
It should hold for the positive $k$:
$k\ge p^{(n-2)/2}$.
And as you can see from this expression, it depends on if $n$ is odd or even .
Even case: the smallest positive $k$ is $p^{(n-2)/2}$, and only
$\{p^{(n-2)/2},2p^{(n-2)/2},3p^{(n-2)/2},\cdots,p^{n}-p^{(n-2)/2}\}$ 
should satisfy your condition as $k$ except 0. The cardinality of this set including 0 is $p^{(n+2)/2}$.
Odd case: the positive smallest $k$ is $p^{(n-1)/2}$, and only
$\{p^{(n-1)/2},2p^{(n-1)/2},3p^{(n-1)/2},\cdots,p^{n}-p^{(n-1)/2}\}$ 
should satisfy your condition as $k$ except 0. The cardinality of this set including 0 is $p^{(n+1)/2}$.
You would wonder this is different from what you see from your numerical experiment, but this is just because of the machine precision of long long int.
