Integer partitioning problem - for fun

  • Context: Undergrad 
  • Thread starter Thread starter Pepper Mint
  • Start date Start date
  • Tags Tags
    Fun Integer
Click For Summary
SUMMARY

The discussion centers on the integer partitioning problem involving two user-input integers, m and n. The system generates a list of M integers based on the formula x_M = x_{M-1} + n, starting from m. After randomly deleting N rows from this list, the challenge arises in deducing the original values of m and n without retaining them in memory. Participants suggest statistical analysis of the differences between the remaining integers to infer possible values for m and n, emphasizing the necessity of knowing N and M for accurate deductions.

PREREQUISITES
  • Understanding of integer sequences and partitioning
  • Familiarity with basic statistical analysis techniques
  • Knowledge of algorithmic complexity and memory constraints
  • Proficiency in programming concepts related to list manipulation
NEXT STEPS
  • Research statistical methods for inferring missing data
  • Explore algorithms for generating integer sequences
  • Learn about memory-efficient data structures in programming
  • Investigate the implications of random deletions in data sets
USEFUL FOR

This discussion is beneficial for mathematicians, computer scientists, and software developers interested in algorithm design, particularly those tackling problems related to data recovery and statistical inference in integer sequences.

Pepper Mint
Messages
91
Reaction score
139
I have a user input of 2 integers (m,n)
Then my system will generate 1 list of M (m,n < M) integers that start at m and end at Mth integer of value xM. The formula to calculate xM is followed by
x_0=m
x_M=x_{M-1}+n
After the list is generated I randomly delete N (N << M) rows from it and given that my system isn't allowed to remember (m,n), how can I find out what values (m,n) were ?

For example
(m,n)=(2,5)
M=5 => L={2,7,12,17,22}
deleting L2,4 yields L={2,12,22}
 
Mathematics news on Phys.org
In general case you can't.

I would start checking what all xi-xi-1 (actually every xi-xj) have in common.
 
  • Like
Likes   Reactions: Pepper Mint
As Borek says, you can't do this if you don't know ##N## and ##M##. But you can statistically analyze what the ##n## and ##m## values likely might have been.
 
  • Like
Likes   Reactions: Pepper Mint

Similar threads

Replies
7
Views
2K
  • · Replies 6 ·
Replies
6
Views
3K
  • · Replies 7 ·
Replies
7
Views
3K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 7 ·
Replies
7
Views
3K
  • · Replies 7 ·
Replies
7
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 125 ·
5
Replies
125
Views
20K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 27 ·
Replies
27
Views
5K