TopCoder Statistics - Problem Statement

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}.
1

Returns: 1
2

Returns: 1
3

Returns: 2
4

Returns: 2
5

Returns: 2
6

Returns: 2
7

Returns: 3
8

Returns: 2
9

Returns: 3
10

Returns: 3
76

Returns: 5
14

Returns: 3
1947478536

Returns: 25
11

Returns: 3
12

Returns: 2
13

Returns: 3
16398

Returns: 10
19

Returns: 4
21

Returns: 4
875719702

Returns: 24
894486

Returns: 14
519702

Returns: 13
1902399512

Returns: 25
26

Returns: 3
27

Returns: 4
37

Returns: 4
41

Returns: 4
51109418

Returns: 19
896422958

Returns: 23
567

Returns: 8
124989

Returns: 13
62

Returns: 5
1987637823

Returns: 25
1093360709

Returns: 23
9292

Returns: 9
1908527694

Returns: 24
2132

Returns: 8
108

Returns: 4
1146483

Returns: 16
1482867

Returns: 17
267380

Returns: 13
1955496058

Returns: 24
882810

Returns: 16
124

Returns: 5
30758014

Returns: 21
127

Returns: 7
1305216

Returns: 16
10236546

Returns: 17
2183

Returns: 9
1961909895

Returns: 25
137

Returns: 5
4707981

Returns: 18
608911

Returns: 16
875092130

Returns: 21
2212

Returns: 8
166

Returns: 6
1974695083

Returns: 24
643758

Returns: 15
182447

Returns: 14
70092978

Returns: 19
188

Returns: 6
1945998526

Returns: 26
394332362

Returns: 21
116963

Returns: 12
1918743784

Returns: 24
24315

Returns: 13
2304

Returns: 7
15624

Returns: 9
3298058

Returns: 17
16625940

Returns: 17
277

Returns: 6
1960903495

Returns: 25
332

Returns: 6
4431

Returns: 10
62787920

Returns: 20
521736534

Returns: 21
1980216669

Returns: 25
433612126

Returns: 23
442221

Returns: 16
369

Returns: 7
98675

Returns: 13
750198133

Returns: 24
802174

Returns: 16
1915712385

Returns: 24
8072

Returns: 9
463249

Returns: 13
396738453

Returns: 23
1965666712

Returns: 24
1958328732

Returns: 22
2196388

Returns: 16
1907003812

Returns: 24
1975741864

Returns: 23
1956055470

Returns: 24
389556

Returns: 14
202679

Returns: 15
4813764

Returns: 16
453

Returns: 7
11206

Returns: 11
900163526

Returns: 23
61641679

Returns: 21
112601

Returns: 13
1940642777

Returns: 24
1915380713

Returns: 23
53228

Returns: 12
486381

Returns: 16
1968165869

Returns: 25
7159279

Returns: 19
5104

Returns: 10
469488

Returns: 13
16881

Returns: 12
1293764087

Returns: 24
127993

Returns: 14
1234567899

Returns: 23
1124565465

Returns: 23
1999999994

Returns: 23
1899894091

Returns: 25
2000000000

Returns: 24
873

Returns: 8
999999492

Returns: 22
30

Returns: 4
1000000007

Returns: 23
38

Returns: 4
367567200

Returns: 20
1999999999

Returns: 25
994010

Returns: 15
90

Returns: 5
999999925

Returns: 24
54

Returns: 4
1000000000

Returns: 24
901740842

Returns: 23
348567397

Returns: 23
806400

Returns: 15
1073741823

Returns: 30
1989187200

Returns: 22
822784415

Returns: 24
29

Returns: 4

Statistics

Problem Statement for "DivisorSequences"

Problem Statement

Definition

Constraints

Examples