Iterative Algorithms and Control Flow in Problem Solving

Problem 9: Sum of Consecutive Integers Raised to Power k

  • Problem Objective: Calculate the sum of consecutive integers starting from 11 up to a given limit nn, where each consecutive integer is raised to the power of kk:   ∑i=1nik\sum_{i=1}^{n} i^k

  • Input Parameters:

    • An upper limit integer nn (for example, n=10n = 10).
    • An exponent value kk.
  • Algorithm and Implementation Steps:

    • Initialize an accumulator variable total to 00.
    • Utilize a for loop to iterate through consecutive numbers starting from 11 up to nn.
    • Account for loop boundary mechanics: In standard for loop implementations (such as Python's range), the upper limit is excluded. To include nn, the loop must iterate up to n+1n + 1.
    • In each iteration ii, compute the term iki^k.
    • Increment total by adding the computed power iki^k to the accumulated value.
    • Upon completing all iterations from 11 to nn, write out the final computed sum in total.

Problem 10: Computing Factorial of n

  • Factorial Definition: The factorial of a non-negative integer nn, denoted as n!n!, is defined as the product of all consecutive positive integers starting from 11 up to nn:   n!=∏i=1ni=1×2×3×⋯×nn! = \prod_{i=1}^{n} i = 1 \times 2 \times 3 \times \dots \times n

  • Input Parameters:

    • A single integer input nn (for example, n=10n = 10).
  • Algorithm and Loop Logic:

    • The control flow mirrors Problem 9 by employing a for loop over consecutive integers from 11 to nn, but substitutes addition with multiplication.
    • Initialization Rule for Accumulators:
    • When computing a sum, the accumulator must be initialized to 00.
    • When computing a running product (multiplication), the accumulator/result variable must be initialized to 11.
    • Initializing a multiplicative accumulator to 00 causes every subsequent iteration to multiply by zero, resulting in an incorrect final product of 00.
    • In each loop iteration, multiply the running result by the current integer ii.
    • After all iterations finish, output the final product representing n!n!.

Problem 11: Generating the nth Fibonacci Number Using While Loops

  • Problem Objective: Compute and output the nn-th number in the Fibonacci sequence given a single command-line argument nn.

  • Sequence Logic: In the Fibonacci sequence, each number is generated by adding the previous number to the current number.

  • State Variables and Initialization:

    • Set initial state variable a=−1a = -1.
    • Set initial state variable b=1b = 1.
    • Set loop counter variable i=0i = 0.
  • Loop Execution Steps:

    • Execute a while loop with the continuation condition: i≤ni \le n.
    • Inside each iteration of the loop, perform an exchange/update of sequence values:
    • Update aa to hold the current sequence value from bb.
    • Update bb to hold the sum of the previous and current values (a+ba + b).
    • Increment the iteration counter ii by 11.
    • Loop termination occurs when i>ni > n, confirming that exactly nn iterations have completed.
    • Output the final value stored in bb, which represents the nn-th number in the sequence.
  • Loop Construct Requirement:

    • While the problem can computationally be implemented using a for loop, the assignment explicitly requires using a while loop.

Problem 12: Primality Testing Algorithm

  • Problem Objective: Take a single integer command-line argument nn and determine whether nn is a prime number, returning a boolean value (true if prime, false if not prime).

  • Divisibility Testing Logic:

    • Initialize divisor candidate i=2i = 2.
    • Execute a while loop with the condition: i≤nii \le \frac{n}{i}.
    • This condition tests whether there is any possible factor up to the square root of nn.
    • For each iteration, test divisibility using the modulo operator to see if nn is divisible by ii:
    • If nn is evenly divisible by ii, a divisor exists, confirming that nn is composite (not prime). Break out of the loop and return the non-prime status (false).
    • If nn is not divisible by ii, increment ii by 11 (i=i+1i = i + 1) and continue testing successive integers (22, 33, and so forth).
    • If the loop terminates because i>nii > \frac{n}{i} without finding any divisor, nn has no divisors and is confirmed to be prime (true).

Problem 13: Counting Primes in a Given Range

  • Problem Objective: Take an integer command-line input nn and count the total number of prime numbers within the range from 11 to nn.

  • Dependency on Problem 12:

    • Solving Problem 13 requires using the primality testing function implemented in Problem 12.
  • Algorithm and Nested Loop Structure:

    • Read command-line argument nn.
    • Initialize a prime counter variable count = 0.
    • Execute an outer for loop iterating variable ii over the range from 22 up to nn.
    • For each value of ii, execute the nested primality logic (the while loop check from Problem 12):
    • If the inner check evaluates that ii is prime, increment count by 11.
    • If ii is not prime, do not increment count; move immediately to the next iteration of the outer loop.
    • Step-by-step evaluation trace for initial values:
    • For i=2i = 2: Test if prime. Since 22 is prime, increment count by 11.
    • For i=3i = 3: Test if prime. Since 33 is prime, increment count by 11.
    • For i=4i = 4: Test if prime. Since 44 is not prime, do not increment count.
    • For i=5i = 5: Test if prime. Since 55 is prime, increment count by 11.
    • Continue this process sequentially up to the upper limit nn.
    • Output the final accumulated integer value of count.

Problem 14: Identifying Perfect Numbers

  • Definition of Perfect Numbers: A positive integer is a perfect number if it is equal to the sum of its proper positive divisors (excluding the number itself).

  • Problem Objective: Find all perfect numbers less than or equal to an input integer nn.

  • Algorithm and Execution Steps:

    • Take command-line input integer nn.
    • Run an outer loop iterating variable ii over the range from 22 up to nn.
    • For each candidate number ii:
    • Initialize total = 0.
    • Iterate a divisor candidate jj through the range starting from 11 up to half of the current number:       1≤j≤i21 \le j \le \frac{i}{2}
    • Check if jj divides ii without remainder.
    • If jj divides ii, increment total by adding jj to it.
    • After testing all possible divisors up to i2\frac{i}{2}, compare the accumulated total against ii:
      • If total == i, ii is a perfect number.
      • Print the number ii directly to standard output.
      • If total != i, do not print the number and continue to the next candidate.
  • Operational Difference Between Problem 13 and Problem 14:

    • In Problem 13, prime numbers are counted using a running accumulator, and only the single scalar total count of primes is output.
    • In Problem 14, occurrences are not aggregated into a count; instead, each qualifying perfect number is printed individually as it is discovered.

Problem 15: Finding Ramanujan Numbers

  • Definition and Mathematical Formulation: A Ramanujan number (also known as a taxicab number) is an integer that can be expressed as the sum of two positive cubes in two distinct ways:   x=a3+b3=c3+d3x = a^3 + b^3 = c^3 + d^3   where aa, bb, cc, and dd are positive integers, and the pairs (a,b)(a, b) and (c,d)(c, d) are distinct.

  • Problem Objective: Given an upper limit nn, test each number in the range from 11 to nn to check if it is a Ramanujan number, and output the full equality equation when found.

  • Loop Mechanics and Pruning Conditions:

    • Search bounds are pruned early: if any single cubed term exceeds nn, the sum of two cubes must also exceed nn, making the combination invalid.
    • Initialize the first term: set a=1a = 1.
    • Condition 1: Check if a3≤na^3 \le n. If a3>na^3 > n, terminate/break the loop immediately.
    • Initialize the second term: set b=a+1b = a + 1.
    • Condition 2: Check if a3+b3≤na^3 + b^3 \le n. If a3+b3>na^3 + b^3 > n, break the inner loop for bb.
    • Search for a second distinct pair (c,d)(c, d):
    • Set c=a+1c = a + 1.
    • Condition 3: Check if c3≤nc^3 \le n. If c3>nc^3 > n, break the loop.
    • Set dd and check if c3+d3≤nc^3 + d^3 \le n. If c3+d3>nc^3 + d^3 > n, the condition is not satisfied.
    • Equivalence Validation:
    • Assign x=a3+b3x = a^3 + b^3.
    • Assign y=c3+d3y = c^3 + d^3.
    • Compare xx and yy: check if x==yx == y.
    • If x==yx == y, the condition is satisfied: output the equation displaying x=a3+b3=c3+d3x = a^3 + b^3 = c^3 + d^3.
    • Variable Increments:
    • Increment the search values in reverse nested order: increment dd by 11, then cc by 11, then bb by 11, then aa by 11.

Assignment Submission and Documentation Guidelines

  • In-Code Comments: Code must contain clear comments throughout explaining the purpose, control flow, and logic of each section.

  • Notes File Requirements:

    • Provide a clear narrative summary detailing what was accomplished.
    • Detail the specific technical problems and obstacles encountered while working through each problem.
    • Detail the exact steps and troubleshooting approaches taken to resolve those obstacles.
    • Do not simply list library or tool names (e.g., stating "I used this particular library"). The documentation must explain how the library was applied, what challenges arose during its integration, and how those challenges were resolved.

Questions and Discussion

  • Question: Will points be deducted if Problem 11 is solved using a for loop instead of a while loop?

    • Response: Yes, points will be deducted because the assignment instructions explicitly specify using a while loop. Exploring alternative implementations using for loops is encouraged for learning and understanding how loop mechanisms work, but the submitted solution must strictly adhere to the while loop instruction.
  • Additional Inquiries: Help and support for assignment questions are available directly with Jacob and Gia.