I'm in need of storing a large number, millions, of files on disk. I want to use a sharding directory structure so there is no more than a thousand files in a directory. If I use 3 directories deep, I can get a billion files (1000^3).

My math is a little rusty and I'm not sure the correct formula to figure out what directory a file would land in given an integer key for the file.

For example, file '0010.pdf' would land in the directory '0000\0000\0000\0010.pdf'. File '2010.pdf' would go in '0000\0000\0002\0010.pdf'. So the structure is '{level 1}{level 2}{level 3}{file}'.

How do I mathematically figure out the various levels? I'm looking for a formula. C# code would be even better, but I can derive that from the formula if need be.

**Edit**

I converted the answer below to a c# function.

```
public static string Shard(long key, string extension, int maxFiles = 1000, int depth = 3)
{
    var parts = new List<string>();
    long current = key;

    for (int i = depth; i > 0; i--)
    {
        long q = Convert.ToInt64(Math.Pow(maxFiles, i));
        long level = current / q;

        parts.Add(string.Format("{0:0000}", level));

        current = current % q;
    }

    parts.Add(string.Format("{0:0000}{1}", current, extension));

    string separator = Path.DirectorySeparatorChar.ToString(CultureInfo.InvariantCulture);
    string path = string.Join(separator, parts);

    return path;
}

```