Koko kierros

Aluksi listalla on kokonaisluvut $[1,2,3,...,n]$ nousevassa järjestyksessä. Joka askeleella otat listan kaksi ensimmäistä alkiota ja siirrät ne listan loppuun käänteisessä järjestyksessä. Monenko askeleen jälkeen listan alkuperäinen järjestys on palautunut?

Esimerkiksi tapauksessa $n=5$ listan sisältö on aluksi $[1,2,3,4,5]$ ja muuttuu sitten seuraavasti:

• $[3,4,5,2,1]$
  
• $[5,2,1,4,3]$
  
• $[1,4,3,2,5]$
  
• $[3,2,5,4,1]$
  
• $[5,4,1,2,3]$
  
• $[1,2,3,4,5]$
  

Tässä tapauksessa siis $6$ askeleen jälkeen listan järjestys on palautunut.

Voit olettaa, että $n$ on välillä $2 \dots 10^9$. Huomaa, että $n$ on suuri, joten ei ole mahdollista luoda niin suurta listaa ja simuloida prosessia, vaan sinun tulee keksiä tehokkaampi algoritmi.

Python

Toteuta tiedostoon fullround.py funktio count, joka antaa askelten määrän.

def count(n):
    # TODO

if __name__ == "__main__":
    print(count(2)) # 2
    print(count(5)) # 6
    print(count(31)) # 240
    print(count(1234567)) # 381038919372

Java

Toteuta tiedostoon FullRound.java metodi count, joka antaa askelten määrän.

public class FullRound {
    public long count(int n) {
        // TODO
    }

    public static void main(String[] args) {
        FullRound f = new FullRound();
        System.out.println(f.count(2)); // 2
        System.out.println(f.count(5)); // 6
        System.out.println(f.count(31)); // 240
        System.out.println(f.count(1234567)); // 381038919372
    }
}