# Parity of number of divisors

Im pretty new here.

My question showing me an algorithm:

TRUE_SEQ(A[1...n])

for i <- 1 to n do
A[i] <- FALSE
for i <- 1 to n do
k <- i
while(k <= n) do
FLIP(A[k])
k <- k + i

FLIP(x)

if x = TRUE then
x <- FALSE
else
x <- TRUE

Now i need to prove that after we finish TRUE_SEQ, the value of $$A[i]$$ is TRUE if and only if $$i \in N$$ is a power of a some natural number.

We learned about loop recorded sequence (Im not sure if i say it correctly in english)

Any way i would like a hint (and prefer a hint than a solution - as those are my homeworks)

Thank you for the help.

• The question does not make sense. Every number $i\in \mathbb{N}$ is a power of a natural number, namely $i^1$. And $4=2^2$ will be A[4]=true but $8=2^3$ will be A[8]=false. Apr 2 '20 at 16:49
• power of a natural number, eg, 3 is not a power of any natural number, because there is not an $x \in N$ such that $3 = x^2$
– Alon
Apr 2 '20 at 16:51
• Welcome. Can you rename your title to something more specific? That will help people understand your question better.
– 6005
Apr 2 '20 at 16:55
• I dont have an idea for something more specific, i know its pretty general, but i dont have an idea for specificity. Thanks
– Alon
Apr 2 '20 at 16:57
• Next time, I suggest running the algorithm and seeing what the output is. This is how you would discover that the TRUE positions correspond to squares. Apr 2 '20 at 19:12

At the end of the algorithm, the value of $$A[n]$$ is the parity of the number of divisors of $$n$$ (TRUE means odd parity). The divisors of $$n$$ come in pairs $$i,n/i$$. Most of these pairs consist of two distinct values, but if $$n$$ is a square, then when $$i = \sqrt{n}$$, both elements are equal. This shows that $$A[n]$$ is TRUE if and only if $$n$$ is a square.