Odd Catalan numbers P75985


Statement
 

pdf   zip

html

The famous Catalan numbers can be defined by the recurrence

Cn = 
n−1
i=0
 Ci · Cni−1   ,

with C0 = 1. The first Catalan numbers are 1, 1, 2, 5, 14, 42, 132, …

You are given an index i. What is the smallest j such that ji and Cj is odd?

Input

Input consists of several cases, each with a natural number no larger than 1015.

Output

For every i, print the smallest j such that ji and Cj is odd. If such a number does not exist, print “Catalans are strange!”.

Public test cases
  • Input

    0
    1
    2
    3
    1099511627768
    

    Output

    0
    1
    3
    3
    1099511627775
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Tretzè Concurs de Programació de la UPC - Final
    Date
    2015-09-16