1
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 2 '20 at 16:49
  • $\begingroup$ 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$ $\endgroup$
    – Alon
    Apr 2 '20 at 16:51
  • $\begingroup$ Welcome. Can you rename your title to something more specific? That will help people understand your question better. $\endgroup$
    – 6005
    Apr 2 '20 at 16:55
  • $\begingroup$ I dont have an idea for something more specific, i know its pretty general, but i dont have an idea for specificity. Thanks $\endgroup$
    – Alon
    Apr 2 '20 at 16:57
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 2 '20 at 19:12
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.