Finding the Next Smith Number

A Smith number is a composite integer n such that the sum of the decimal digits of n equals the sum of the decimal digits of all its prime factors, counting multiplicities. To example, 666 = 2 × 3 × 3 × 37 gives digit sums 6+6+6 = 18 and 2+3+3+3+7 = 18.

A brute-force procedure can be designed to locate the smallest Smith number that is larger than a given positive integer N:

1. Write a helper that computes the sum of the decimal digits of an integer.
2. Implement a test isSmithNumber(x) that first rejects primes (and numbers below 4), then performs trial division to obtain the sum of digits of all prime factors.
3. Starting from N+1, repeatedly check candidates until isSmithNumber returns true.

Implementation in C

#include <stdio.h>

int digitSum(int num) {
    int total = 0;
    while (num > 0) {
        total += num % 10;
        num /= 10;
    }
    return total;
}

int isSmithNumber(int n) {
    if (n < 4)
        return 0;

    // Do not accept primes – quick primality check up to sqrt(n)
    for (int d = 2; d * d <= n; d++) {
        if (n % d == 0)
            break;
        if (d * d > n)   // reached end of loop without divisor
            return 0;
    }

    int factorDigitSum = 0;
    int remainder = n;

    for (int p = 2; p * p <= remainder; p++) {
        while (remainder % p == 0) {
            factorDigitSum += digitSum(p);
            remainder /= p;
        }
    }

    // If remainder > 1, it is a prime factor
    if (remainder > 1)
        factorDigitSum += digitSum(remainder);

    return factorDigitSum == digitSum(n);
}

int main(void) {
    int N;
    scanf("%d", &N);

    int candidate = N + 1;
    while (!isSmithNumber(candidate))
        candidate++;

    printf("%d\n", candidate);
    return 0;
}

Complexity

For a single candidate m the primality test and trial division both run in O(√m) time, while digit sums require O(log m) operations. The outer loop may examine many numbers before finding a Smith number; therefore the entire procedure is in practice unpredictable, but15the per-candidate16bound is O(√m).17Space complexity is O(1).

Counting Inversions in an Array

Given an array A of length n, a pair (i, j) with i < j and A[i] > A[j] is called an inversion. The total number of inversions can be obtained by two straightforward brute-force strategies.

Straightforward Double Loop

Iterate over every pair (i, j) where i < j and increment a counter whenever A[i] > A[j].

#include <stdio.h>
#include <stdlib.h>

int countInversionsLoop(const int arr[], int n) {
    int inversions = 0;
    for (int left = 0; left < n; left++) {
        for (int right = left + 1; right < n; right++) {
            if (arr[left] > arr[right])
                inversions++;
        }
    }
    return inversions;
}

Recursive Brute Force

A recursive formulation decomposes the problem:11count inversitions that involve the first element, then recursively process the rest of the array. The recursion stops when a sub-array has fewer than two elements.

int countInversionsRec(const int arr[], int len) {
    if (len <= 1)
        return 0;

    int count = 0;
    // Compare first element with every element to its right
    for (int j = 1; j < len; j++) {
        if (arr[0] > arr[j])
            count++;
    }

    // Recursively process the rest of the array
    return count + countInversionsRec(arr + 1, len - 1);
}

Integration and Complexity

Both approaches can be called from a simple main that reads the|array size and elements, then prints the result.

int main(void) {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);
    int *arr = (int*)malloc(n * sizeof(int));
    printf("Enter elements: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    printf("Inversions (double loop): %d\n", countInversionsLoop(arr, n));
    printf("Inversions (recursive):  %d\n", countInversionsRec(arr, n));

    free(arr);
    return 0;
}

Time complexity: Both the double-loop and the recursive implementations examine every ordered pair (i, j) with i < j, resulting in about n(n-1)/2 comparisons. Hence they run in O(n²) time.

Space complexity: The iterative loop uses O(1) auxiliary space. The recursive method uses O(n) call-stack space in the worst case (when the array is6000large enough to recurse n levels deep).6The9input array itself occupies O(n) memory in both cases.