🔗TL;DR

A while ago I saw a reddit post with the title “Solve the problem without using a loop”. The post linked a screenshot of a code snippet that looked like this:

//Write a program to print all even numbers from 1 to 500

#include <stdio.h>

void main(){
    printf("2\n");
    printf("4\n");
    printf("6\n");
    printf("8\n");
    printf("10\n");
    printf("12\n");
    printf("14\n");
    printf("16\n");
    printf("18\n");
    printf("20\n");

In the comment section there were a lot of ideas how to solve that without loops. Most of the solutions are not valid solutions if you ask me and so I gave it a try to really solve it without any loops.

Here is the solution I came up with:

import locale
locale.setlocale(locale.LC_ALL, 'en_US.UTF-8')

a = 250
b = 10 ** 3
c = b ** a
d = b * c
e = b - 1
f = a * (e * (c-1) + c - d) + d - b
g = (f*2) // (e**2)

formatted_output = locale.format_string("%d", g, grouping=True).zfill(e).replace(',', '\n')

print(formatted_output)

🔗Invalid Solutions

Let’s walk through some of the other solutions in the comment section and I’ll explain why I think these solutions are invalid (by my totally arbitrary and made up rules).

🔗Solutions that aren’t

printf("all even numbers from 1 to 500");

This “solution” clearly prints “all even numbers from 1 to 500”, but I guess someone took the exercise too literally 😂

🔗Hard-code everything

printf("2\n4\n6\n8\n10\n12\n...

It’s true, it solves the problem without loops but to do that either you have to write everything by hand - which doesn’t scale well and is error prone - or you have to write a program with a loop that outputs the hard-coded string. So I consider solutions that just hardcode the entire output invalid.

🔗Goto

#include <stdio.h>
void main(){
    int i = 0;
    print: printf("%d", i+=2);
    if(i<=500) goto print;
}

In my eyes this is clearly a loop, it’s just implemented with goto instead of for or while. Also invalid if you ask me.

🔗Recursion

void f(int print_me) {
    printf("%i\n", print_me);
    if (print_me < 500)
        f(print_me + 2);
}

This commenter’s solution was a recursive function. Typically this is done the other way round and tail recursions are converted into equivalent loops as an optimization step. Theoretically all loops can be transformed into a recursion, so this recursive solution is also a loop in disguise and thus invalid.

🔗Iterator pattern

Console.Write(
    string.Join(
        '\n',
        Enumerable.Range(1, 250).Select(x => (x * 2).ToString())
    )
);

I also consider the iterator pattern cheating. The loop itself is just hidden in some helper functions and methods.

🔗Finding a valid solution

We already saw some examples, which I wouldn’t consider valid solutions, here are the (again - completely arbitrary) “rules” so far:

1. The program must output the correct solution (obviously)
2. Hard-coding the output is not allowed
3. Loops in disguise are not allowed
   • goto
   • recursion
   • iterators

Note that rule 3 doesn’t forbid all calls to functions that loop internally, because that would also exclude basically all print functions because they loop internally over all the characters to print them. Rule 3 only forbids function calls that are used to hide the loop that is used to run from 1 to 500.

🔗Step by step

To get a feeling for how to create such a number we start by playing around with some numbers and expressions.

$$ \text{we start with 1} $$ $$ \text{multiply by } 2\text{‘}000 \text{ to shift to the left and double} $$ $$ \text{now we repeat} $$ $$ \text{+1} \rarr 2\text{’}001 $$ $$ \text{×2’000} \rarr 4\text{‘}002\text{’}000 $$ $$ \text{+1} \rarr 4\text{‘}002\text{’}001 $$ $$ \text{×2’000} \rarr 8\text{‘}004\text{’}002\text{’}000 $$

Now we are on the way of constructing a large number that contains smaller numbers, namely the powers of two.

$$ 2^x \rarr 1, 2, 4, 8, 16, 32, … $$

But currently we still need a loop to add 1 and multiply by 2000, but luckily in mathematics there are operations that are basically loops. For example you can think of multiplication as a looped addition and exponentiation as a looped multiplication.

Our squares can also be constructed with a geometric series

$$ 2000^0 + 2000^1 + 2000^2 + 2000^3 + 2000^4 + … $$ $$ \text{which can also be written as} $$ $$ \sum_{i=0}^n 2000^i $$

Because I’m too lazy to derive it myself (and not smart enough, but let’s not tell anyone) we look up the closed-form formula on Wikipedia for the first $n$ terms.

$$ \frac{1-r^n}{1-r} $$ $$ \small\text{multiply top and bottom by -1 and replace r with 2’000} $$ $$ \frac{2\text{‘}000^n - 1}{2\text{’}000 - 1} $$ $$ \small\text{when we now set n to 5, we get the five first terms of the powers of two} $$ $$ 16\text{‘}008\text{’}004\text{‘}002\text{’}001 $$

Now we want to do a similar thing with the original exercise, namely printing even numbers. To make things simpler we start by developing a formula to print the even numbers from 1 to 10. We start by writing out what the number should look like.

$$ \overlinesegment{02}\overlinesegment{04}\overlinesegment{06}\overlinesegment{08}\overlinesegment{10}\ $$

Of course the trailing zero isn’t really there, we deal with that later. Because we are only interessted in the even numbers we extract out that factor of two and first develop a method to get the number

$$ N = \overlinesegment{01}\overlinesegment{02}\overlinesegment{03}\overlinesegment{04}\overlinesegment{05}\ $$

Keep in mind that we have to reserve enough space for each number so they don’t overflow into the neighbouring numbers. In this case we reserve two digits for every number, so in base 10, that’s a factor of $10^2 = 100$. Notice that the most significant digits of the large number N represent the small numbers and the least significant digits of N the large numbers. As a sum it would look like this:

$$ N = 5 + 400 + 30000 + 2000000 + 100000000 $$ $$ N = 5\cdot100^0 + 4\cdot100^1 + 3\cdot100^2 + 2\cdot100^3 + 1\cdot100^4 $$

In this first draft the exponents are increasing but the coefficient is decreasing. To write it as a sum we have to make sure we have a single increasing variable i that starts at zero, so we have to restructure the sum a bit

$$ N = (5-0)\cdot100^0 + (5-1)\cdot100^1 + (5-2)\cdot100^2 + (5-3)\cdot100^3 + (5-4)\cdot100^4 $$ $$ \small\text{for n = 5:} $$ $$ \quad\sum_{i=0}^{n-1} (n-i)\cdot100^i = 102030405 $$

For the original exercise we need to go bigger. Because we now have larger numbers (up to three digits) we have to reserve more space, so we switch from 100 to 1000, but besides that, everything else is the same.

$$ \small\text{for n = 250:} $$ $$ \quad\sum_{i=0}^{n-1} (n-i)\cdot1000^i = 102030405 $$

$$ =\quad\overlinesegment{\quad1}\overlinesegment{002}\overlinesegment{003}\overlinesegment{004}…\overlinesegment{248}\overlinesegment{249}\overlinesegment{250} $$

But how do we calculate that now in our program without using a loop again to sum up all items? We again lookup the closed-form formula on Wikipedia. But in contrast to our example with the square numbers this is not a geometric series, because the coefficient is not constant but itself an arithmetic sequence. Fortunately math also has us covered here. This kind of sequence is called Arithmetico-geometric sequence. Here is the formula for the sum of the first n terms:

$$ S_n = \sum_{k = 1}^n \left[a + (k - 1) d\right] br^{k - 1} $$ $$ = \frac{ab - (a+nd) \ br^n}{1 - r}+\frac{dbr\ (1 - r^n)}{(1-r)^2} $$

The formula we stole™ from Wikipedia is pretty generic so we simplify it and determine the parameters during the process.

$$ \underbar{\small\text{start with k=0}} $$ $$ \quad S_n = \sum_{k = 0}^{n-1} \left[a + kd\right] br^k $$ $$ \underbar{\small\text{b=1, d=-1, r=1000}} $$ $$ \quad S_n = \sum_{k = 0}^{n-1} \left[a - k\right] \cdot 1000^k $$ $$ \underbar{\small\text{substitute i for k, n=250, a=250}} $$ $$ \quad S_{250} = \sum_{i = 0}^{249} \left(250 - i\right) \cdot 1000^i $$

🔗Implementation

Next step is to substitute the parameters we found into the closed-form formula, simplify again and identify some common constants so the code later doesn’t look too messy. After a few steps (which I’ll skip here because they are boring) we have something like this:

$$ 250\cdot \left(\frac{1-10^{3\cdot250}}{1-10^{3}}\right) - \left(\frac{10^3-250\cdot10^{3\cdot250}+249\cdot10^{3\cdot251}}{999^2}\right)$$

At this point we have everything we need to start writing code. Next we have to decide in what language. Theoretically you can use any language you like the only things you need are simple math operations for large integers (often called big int, big integer or big num) including exponentiation. The large integer support is needed because the integer we’ll construct is 750 digits long.

I chose Python because it uses (aka. transparently transitions) to big integers and it has a very convenient power operator **. To print the numbers on separate lines I use format_string to add group separators, zfill to fix the missing leading zeros in the string representation for the first number and replace to finally replace the group separators introduced by format_string with new line characters.

import locale
locale.setlocale(locale.LC_ALL, 'en_US.UTF-8')

a = 250
b = 10 ** 3
c = b ** a
d = b * c
e = b - 1
f = a * (e * (c-1) + c - d) + d - b
g = (f*2) // (e**2)

formatted_output = locale.format_string("%d", g, grouping=True).zfill(e).replace(',', '\n')

print(formatted_output)

Try it out on ideone.com: https://ideone.com/VUgI6t

There are “hidden” loops inside format_string, zfill, replace and print and as stated earlier I don’t consider them cheating, because they are not used to hide a loop from 1 to 500.