Stripe Batch ID Parity
Stripe processes an immense volume of financial transactions daily. For internal analytics, reconciliation, and load-balancing purposes, transactions are often grouped into batches, each identified by a unique integer ID. These batch IDs sometimes need to satisfy specific mathematical properties to ensure data integrity or optimize system performance. One such property relates to the parity (even or odd) of the sum of positive divisors of a batch ID. Your task is to efficiently count such batch IDs within a given large range.
Implement a function countOddDivisorSumBatches that takes two BigInt numbers, L and R, representing a closed range [L, R]. The function should return the total count of integers N within this range (inclusive) such that the sum of positive divisors of N is odd.
L: BigInt, the lower bound of the range (inclusive).R: BigInt, the upper bound of the range (inclusive).BigInt, the total count of numbers N in [L, R] whose sum of positive divisors is odd.N (sigma(N)) includes 1 and N itself.L and R can be extremely large, up to 10^18, requiring efficient algorithms that do not iterate through the range.[L, R] is inclusive, meaning both L and R can be valid batch IDs.Examples
Example 1
Input:
L = 1n, R = 10n
Output:
5n
Note:
The numbers in the range [1, 10] whose sum of positive divisors is odd are: 1 (sigma(1)=1), 2 (sigma(2)=3), 4 (sigma(4)=7), 8 (sigma(8)=15), and 9 (sigma(9)=13). There are 5 such numbers.
Example 2
Input:
L = 100n, R = 120n
Output:
1n
Note:
In the range [100, 120], only 100 has an odd sum of positive divisors (sigma(100) = 217). 100 is a perfect square (10^2). No other numbers in this range satisfy the condition.
Example 3
Input:
L = 999999999999999900n, R = 1000000000000000000n
Output:
1n
Note:
This large range contains only one number with an odd sum of positive divisors: 1,000,000,000,000,000,000 (which is 10^18, a perfect square).
Constraints
1 <= L <= R <= 10^18L and R are integers.BigInt in JavaScript/TypeScript) correctly to prevent overflow or precision issues, and addressing edge cases.Loading editor...