DivisorSequences | Topcoder Archive

Problem Statement

Given a positive integer N, find and return the length of the longest sequence a_1, ..., a_K of positive integers such that:

The sum of all a_i is N.
For each valid i, a_i < a_{i+1}.
For each valid i, a_i divides a_{i+1}.

Definition

Class:: DivisorSequences
Method:: longest
Parameters:: int
Returns:: int
Method signature:: int longest(int N)
(be sure your method is public)

Constraints

N will be between 1 and 2*10^9, inclusive.

Examples

```
15
```
```
Returns: 4
```
The only optimal sequence is {1,2,4,8}. Clearly, 1 divides 2, 2 divides 4, 4 divides 8, and 1+2+4+8 = 15.
```
12
```
```
Returns: 2
```
The are four distinct optimal sequences: {1,11}, {2,10}, {3,9}, and {4,8}. There is no valid sequence with more than two elements.
```
34
```
```
Returns: 4
```
The only optimal sequence is {1, 3, 6, 24}.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.