text:
Finding Collatz-like rules with many loops
This code-challenge is related to the code-golf question Analyzing Collatz-like sequences but the goal is quite different here.
If you are familiar with Collatz-like sequences you can skip to the section "The task".
We define a Collatz-like rule with 3 positive integers:

d > 1 divisor
m > 1 multiplier
i > 0 increment

(In the original Collatz sequence d = 2, m = 3 and i = 1.)
For a Collatz-like rule and a positive integer n starting value we define a sequence s in the following manner:

s(0) = n
if k > 0 and s(k-1) mod d = 0 then s(k) = s(k-1) / d
if k > 0 and s(k-1) mod d != 0 then s(k) = s(k-1) * m + i

An example sequence with d = 2, m = 3, i = 5 and n = 80 will be s = 80, 40, 20, 10, 5, 20, 10, 5, 20, ....
Every sequence will either reach higher values than any given bound (i.e. the sequence is divergent) or get into an infinite loop (for some t and u (t!=u) the s(t) = s(u) equality will be true).
Two loops are said to be different if they don't have any common elements.
The task
You should write a program which finds a Collatz-like rule with many different loops. Your score will be the number of found loops. (You don't have to find all of the possible loops and higher score is better.)
The program could be specialized in any manner to produce the best score.
For proof the program should output the values of d, m, i and the smallest values from every found loop.
Example
For d=3 m=7 i=8 the loops are

LOOP 15 5 43 309 103 729 243 81 27 9 3 1
LOOP 22 162 54 18 6 2
LOOP 36 12 4

So a valid proof with a score of 3 could be

d=3 m=7 i=8 min_values=[1 4 2]

You can validate your result with this Python3 code. The program expects a list of space-separated integers d m i min_value_1 min_value_2 ... as input.

It's not immediately obvious to me that there exist no combination of (d, m, i), all positive, that has infinite amount of loops. Even harder to disprove, who says there exist no algorithm that can produce a combination of (d, m, i) that has a finite but arbitrarily large amount of loops.

@PeterTaylor I thought of that, but i has to be positive, so it can't be 0.

I do not see the challenge, you can just bruteforce up to an arbitrary number...

@flawr Until Peter's answer there was no proof that the number of loops is actually unbounded.

@flawr Finding big primes is still interesting despite the fact that there are simple algorithms that can yield arbitrarily large ones in very long time. I think this is a similar situation. (If you could suggest a modification of the question to make it clearer that would be great.)

I would strongly recommend adding a time limit for this problem. Making the winning criterion a mathematical proof is not really in scope for this site, so rewarding clever algorithms based on their faster speeds seems better.

Java, arbitrary score with relatively small numbers
In my previous answer, I considered only primitive loops. It turns out that there's a massive benefit to be gained by considering more complex loops.
Let the loop structure n_0 ... n_{k-1} denote a loop which has n_0 multiply operations, then a division, then n_1 multiplications, then a division, etc. If we start with x_0 and loop back to x_0 then we get the constraint
-(d^k - m^n) x + (d^{b_0}m^0 + d^{b_1}m^1 + ... + d^{b_{n-1}}m^{n-1}) i

where n = n_0 + ... + n_{k-1} and k > b_0 >= b_1 >= ... >= b_{n-1} with the transitions at points corresponding to division steps.
The big bonus is the divisibility constraint: (d^k - m^n) | i is sufficient for x to exist and doesn't depend on the breakdown of the loop structure. However, because we have small d we have to worry about a new problem.
The map x -> mx + i (mod d) is a permutation of 0 .. d-1, and the length of the cycle which contains 0 places an upper bound on the length of a step in the loop sequence. So we have to pick d to satisfy two constraints: d^k - m^n > 0 and the cycle length of 0 under the permutation x -> mx - m^n is greater than n.
If we do that, though, the net result is that for much smaller increments than in the primitive case we can get a number of loops whose growth is related to necklaces. We have two free variables: in the interests of keeping it simple, we'll pick n = 2k. Then the score is OEIS A082936(k+1).
This program allows you to specify k via the command line. If k isn't specified it defaults to 15 (and will take a while to run).
import java.math.BigInteger;
import java.util.*;

public class PPCG47835 {

    public static void main(String[] args) {
        int k = args.length > 0 ? Integer.parseInt(args[0]) : 15;

        BigInteger TWO = BigInteger.valueOf(2);
        int n = 2 * k;
        // We want d to allow steps of up to n without getting a division "too early".
        BigInteger d, i;
    nd: for (d = BigInteger.valueOf((k + 1) | 1); true; d = d.add(TWO)) {
            i = d.pow(k).subtract(BigInteger.ONE.shiftLeft(n));
            if (i.signum() < 0) continue;

            // Find multiplicative inverse of m and additive inverse of i.
            BigInteger half = d.add(BigInteger.ONE).shiftRight(1);
            BigInteger negI = d.subtract(i.mod(d));
            BigInteger inv = BigInteger.ZERO;
            for (int j = 0; j < n; j++) {
                inv = inv.add(negI).multiply(half).mod(d);
                // If we get a division too early, reject this value of d.
                if (inv.signum() == 0) continue nd;
            }

            break;
        }

        System.out.print(d); System.out.print(" ");
        System.out.print("2 "); // m is hard-coded for optimisation reasons
        System.out.print(i); System.out.print(" ");

        visit(d, i, new int[k], 0, n);
    }

    private static long visit(BigInteger d, BigInteger i, int[] a, int off, int unused) {
        long count = 0;
        if (off == a.length - 1) {
            a[off] = unused;

            if (canonical(a)) {
                BigInteger x0 = BigInteger.ZERO, dj = BigInteger.ONE;
                int tail = 0;
                for (int step : a) tail += step;
                for (int step : a) {
                    x0 = x0.add(dj.shiftLeft(tail));
                    tail -= step;
                    x0 = x0.subtract(dj.shiftLeft(tail));
                    dj = dj.multiply(d);
                }

                // Find min element of loop
                BigInteger x = x0, min = x0;
                for (int step : a) {
                    x = x.add(i).shiftLeft(step).subtract(i).divide(d);
                    if (x.compareTo(min) < 0) min = x;
                }
                System.out.print(min); System.out.print(" ");
                count++;
            }
        }
        else {
            for (a[off] = 0; a[off] <= unused; a[off]++) {
                count += visit(d, i, a, off + 1, unused - a[off]);
            }
        }

        return count;
    }

    private static boolean canonical(int[] a) {
        for (int i = 1; i < a.length; i++) {
            // If (a[i], a[i+1], ..., a[n], a[0], ...) < (a[0], a[1], ..., a[n]) then not canonical
            int cmp = 0;
            for (int j = 0; j < a.length; j++) {
                int l = a[(i + j) % a.length];
                if (l < a[j]) return false;
                if (l > a[j]) { cmp = 1; break; }
            }
        }
        return true;
    }
}

A table of values for small k is
k     d   m                        i                             count            time*
1     5   2                                            1                    1      <  10 ms
2     9   2                                           65                    3      <  10 ms
3    11   2                                         1267                   10      <  10 ms
4    11   2                                        14385                   43      <  10 ms
5    13   2                                       370269                  201      ~  20 ms
6    19   2                                     47041785                 1038      ~ 100 ms
7    19   2                                    893855355                 5538      ~ 200 ms
8    19   2                                  16983497505                30667      ~ 200 ms
9    25   2                                3814697003481               173593      ~   1 s
10   29   2                              420707232251625              1001603      ~   6 s
11   29   2                            12200509761511525              5864750      ~  40 s
12   29   2                           353814783188691825             34769374      ~   5 mins
13   29   2                         10260628712891493325            208267320      ~  30 mins
14   37   2                       9012061295994739864233           1258579654   Est.   3 hours
15   37   2                     333446267951814233346669           7663720710   Est.  20 hours
16   37   2                   12337511914217162067306945          46976034379   Est.   6 days
17   37   2                  456487940826035138224277733         289628805623   Est.  40 days
18   53   2             10888439761782913818653903872953        1794932468571   Est. 200 days
19   53   2            577087307374494432392024159626573       11175157356522   Est.   4 years
20   53   2          30585627290848204916790749477648625       69864075597643   Est.  30 years
21   53   2        1621038246414954860589963598385138149      438403736549145   Est. 200 years
22   53   2       85915027059992607611268286218691365993     2760351032959050   Est.   1 millennium
23   53   2     4553496434179608203397220031607758574013    17433869214973754   Est.   7 millennia
24   53   2   241335311011519234780052665123279669128225   110420300879752990   Est.  50 millennia

* Time estimates are for my desktop and do not take into account Moore's law.
By way of comparison, the primitive loop approach gets a count of 256 with d, m, i
115792089237316195423570985008687907853269984665640564039457584007913129639937 2 [encoded data, 19651 characters]

Fantastic answer! I will digest the details in the next few days.

GolfScript, arbitrary score
~:l 2:m.@?):d\1 l,{m\)?d-*}/abs.{1 m 3$)?-*m@)?d-m(*/}+l,/]' '*

This takes an integer on stdin and outputs a sequence with that many loops, in the input format of the Python tester. The online demo runs it for l = 4 and produces output 17 2 1755 117 405 1365 26325; this fork of the tester verifies it.
Explanation
In order to keep it simple, I restricted the analysis to primitive loops: ones with only one division.
(x -> mx + i)^n = (x -> m^n x + (m^n - 1)/(m-1) i)

so this means that I'm looking for solutions to
m^n x + (m^n - 1)/(m - 1)i = dx

or
(m^n - d) x + (m^n - 1)/(m - 1)i = 0

When n > 0, m > 1, m^n - d != 0 this has exactly one solution for x. m - 1 > 0 and m^n - 1 > 0, so in order for the solution to be positive we require m^n - d < 0, and in order for the solution to be an integer we require d - m^n to be a factor of (m^n - 1)/(m - 1)i.
The rest may already be obvious. We pick the desired score, l. We're going to find primitive loops of length 1 to l, so we want d - m^l > 0. To get a smallish output we pick m = 2, d = 2^l + 1. Then to get an easy guarantee of the divisibility constraints we pick i to be the absolute value of (m - d)(m^2 - d)...(m^l - d).

This was exactly my conjecture why this golf's scoring is flawed - it can be arbitrary. Your answer can however be beat by a solution that provides infinite score, if it exists.

@orlp, what's the distinction you're drawing between arbitrarily large and infinite?

An infinite solution would have one m, d, i combination that would contain an infinite amount of cycles. Your solution can generate a m, d, i for an arbitrary, but finite score. I do not know if an infinite solution exists, but I do not find it obvious that it does not.

It's not obvious that there isn't an infinite solution in that sense, but it would surprise me if there is one. If you fix m, d, and the loop structure (in terms of the sequences of multiply or divide steps) then there are 0 or 1 loops of that structure, and one of the conditions required for it to exist is a divisibility constraint on i. Unless there are an infinite number of loop structures which induce the same divisibility constraint, which would be surprising, any finite i can only satisfy a finite number of them.

Python 3, (d = 2, m = 3, i = 96521425) → Score = 2369
The program below writes the output to collatz.txt, and also prints summaries to the shell.
I used the observation that, if (d, m, i) had a lot of loops, then in general (d, m, i*k) also tended to have a lot of loops for different values of k. I started with (2, 3, 13), and eventually worked i up like so:
13 -> 65 -> 1235 -> 35815 -> 250705 -> 2757755 -> 13788775 -> 96521425

before ending up with the lengthy output that can be found here.
The respective scores of the above chain are (using a bound of 10000):
10 -> 16 -> 28 -> 146 -> 304 -> 535 -> 766 -> 1094

2369 was obtained by bumping the bound up to 100000.
This raises a question similar to the one that @orlp has brought up — if I keep doing this multiplication process, will I always be able to get more and more loops? If anyone can prove that, then they'd probably win :)
from collections import defaultdict
import itertools

def f(d, m, i, bound=1000):
    D = defaultdict(set)
    S = set()

    for j in range(1, bound):
        A = [j]
        B = {j}

        for _ in range(bound):
            if j > bound**3:
                break

            if j % d == 0:
                j //= d

            else:
                j = j*m + i

            if j in B:
                S.add(min(A[A.index(j):]))
                break

            A.append(j)
            B.add(j)

    return S

N = 1000
THRESHOLD = 0
BOUND = 10000

MULTIPLIER = 96521425

with open("collatz.txt", "w") as outfile:
    for d, m, i in itertools.product([2], [3], range(1, N)):
        result = f(d, m, MULTIPLIER*i, bound=BOUND)

        if len(result) > THRESHOLD:
            print(d, m, MULTIPLIER*i, " ".join(map(str, sorted(result))), file=outfile, flush=True)
            print(d, m, MULTIPLIER*i, len(result))

(Proof in progress for a possibly different arbitrary score method)
Pick d, m, i such that d and i are coprime and suppose we have a loop for (d, m, i):
a_0 -> a_1 -> a_2 -> ... -> a_(n-1) -> a_n = a_0

Now pick k coprime to i and d, and we want to look at (d, m, i*k). Consider the number k*a for some a.

If d divides a then d divides k*a, and in this case we map k*a -> k*a/d = k*(a/d).
Otherwise, d can't divide k*a since d and k are coprime, and we map k*a -> m*(k*a) + i*k = k*(m*a + i).

Hence one step for a in (d, m, i) is equivalent to one step for k*a in (d, m, i*k). This forms a bijection between the loop in (d, m, i) with the loop
k*a_0 -> k*a_1 -> k*a_2 -> ... k*a_(n-1) -> k*a_n = k*a_0

in (d, m, i*k).
This means that (d, m, i*k) has at least as many loops as (d, m, i). But since i is coprime to d, we can apply the same reasoning to any loops in (d, m, k).
(This explains why the multiplication method managed to give at least as many loops each time, but the proof is incomplete until I can constrain i, k such it always gives strictly more loops each time).


text:
Words of centuries
I'd like to get a list of words that are strongly connected with a particular time epoch, for example, 19th century, 20th century and 21st century. I suspect that nobody used a word like "smartphone" in 19th and 20th century, and, vice versa, nobody still uses a word like "grubble" anymore in 21th century.
Input data
I have quite a few books, laid out in a following directory structure:

On the first level, you have directories named after years when book was published, i.e. from 1801 to 2015.
On the following levels, there could be individual book files or any number of nested directories (for example, grouping books by authors, by genres, by publishers, etc). Ultimately, there's at least a single book inside every such directory. Let's say that names of these files and directories are limited by whatever's allowed on VFAT filesystem (i.e. \ / : * ? " < > | are not allowed).

No other files exist in this structure (for example, a program file would be located elsewhere, no results of previous runs, temporary files, etc).
All book files have the same pure text format, using only ASCII character set. Words are continuous non-empty character sequences of word characters, i.e. [A-Za-z0-9_]+.

For example, contents of this short book:
Here you go, that's APL13-X for your 4923/YR_3.
have the following words: Here, you, go, that, s, APL13, X, for, your, 4923, YR_3.

Comparison of words is case insensitive, that is Here, here and HERE is the same word.
The task
I want to have a program that, being started in a top directory of this structure, would generate 3 files named 19, 20, 21. Each of these files should contain a list of words which occur only in relevant century books and not in any other century's single book (words separated with a newline). Words can be in any case, but all words given in such file must appear only once.
Sample test cases
If you want a sample test case, feel free to use my one, available either as zip file or git repo.
Scoring
Standard code golf rules apply. Shortest answer (written in a language released before 2015-03-16) wins after 3 weeks would pass (on 2015-04-06). Secondary nominations are "shortest answer in any non-esoteric, general purpose language" and "shortest answer per language".
P.S. Please note that "19th century" is defined as 1801..1900 inclusive, that is 1900 is still 19th.

I'm assuming a full program is required, not just a function?

@bcsb1001: Yes, a full runnable program that traverses directories, finds input files, reads them, performs calculations and then outputs the result in 3 files, as per question.

"I'd like to get a list of words that are strongly connected with a particular time epoch": Are you going to use one of these programs on a more substantial set of txt files?  If so, I'd be interested in the final output.

@NathanMerrill: Not really, that's just a cool task story to tell :) In fact, this task was inspired by one of the tasks I've actually performed on a huge (~20 GB) array of texts - however, that was implemented in massively parallel way on a Hadoop cluster.

Ruby, 231 bytes
require'set'
m=[]
Dir['**/*'].map{|n|(m[(n[0..3].to_i-1)/100-18]||=Set.new).merge(IO.read(n).split(/\W/).map{|x|x.upcase})rescue''}
u=[m[0]-m[1]-m[2],m[1]-m[0]-m[2],m[2]-m[0]-m[1]]
3.times{|i|IO.write"#{i+19}",u[i].to_a.join("\n")}

In slighty more readable form with comments, with lvalues extracted:
require'set'
m = []
Dir['**/*'].map { |n|
  # Determine century from first 4 characters of path
  c = (n[0..3].to_i - 1) / 100
  # Make array indices 1 char long (0-1-2) instead of 2 chars (19-20-21)
  c -= 18
  # Initialize per-century array entry with empty set, if required
  m[c] ||= Set.new
  # Read file as a string, split by words, uppercase everything
  # (not lowercase, because "upcase" saves 2 bytes vs "downcase"),
  # merge into the set we've prepared; ignore any possible exceptions
  # (i.e. trying to read the directory as a string)
  m[c].merge(IO.read(n).split(/\W/).map { |x| x.upcase }) rescue ''
}

# New array of sets with unique words per century
u = [
  m[0] - m[1] - m[2],
  m[1] - m[0] - m[2],
  m[2] - m[0] - m[1]
]

# Output of this array entries, each to individual file
3.times { |i|
  IO.write "#{i + 19}", u[i].to_a.join("\n")
}

R, 284 266
Reads in every file from the specified working directory and uniquely adds their words to the appropriate century word vector.  Each word vector is compared to the others and the words that are not in are written out.
C=as.character;S=strsplit;L=tolower;U=unlist;W=list();for(f in list.files(r=T)){Y=C((strtoi(U(S(f,'/'))[1])-1)%/%100+1);W[[Y]]=unique(L(c(W[[Y]],U(S(scan(f,w=C()),'[^A-Za-z0-9_]',p=T)))))};for(i in 1:3)cat(W[[i]][!L(W[[i]])%in%L(U(W[-i]))],file=names(W)[i],sep='\n')

Caveats:

Assumes the current directory is pointing in the right place.  Otherwise use setwd()
There must be at least one file per century and no additional files outside the 19th, 20th and 21st centuries.

In a more readable form
setwd("some/directory/here");
# Commonly used functions
C=as.character;
S=strsplit;
L=tolower;
U=unlist;
# Initialise word list
W=list();
# for each file in working directory
for(f in list.files(r=T)){
    # Determine century from first part of path.
    Y=C((strtoi(U(S(f,'/'))[1])-1)%/%100+1);
    # Scan the file splitting on non letters/numbers/underscore
    # refreshing the unique list of words for the century
    W[[Y]]=unique(L(c(W[[Y]],U(S(scan(f,w=C()),'[^A-Za-z0-9_]',p=T)))))
    };
# Write out the words for each century that aren't in the other centuries
for(i in 1:length(W))
    cat(W[[i]][!L(W[[i]])%in%L(U(W[-i]))],file=names(W)[i],sep='\n')

Can you remove setwd(...) invocation from your submission? Please assume that there's no need to change working directory, program's current working directory is already the one you would start traversal from. That would bring it down to 275.

Also note that there are always only 3 centuries - probably length(W) would be always 3?

@GreyCat Made the edits you suggested, Thanks.

Shell script (reference solution, 879 bytes)
#!/bin/sh

# This program uses temporary files, but no need to perform any kind
# of cleanup in a real answer.

# Given a stream of lines on the stdin, rejects all lines that match
# lines in a file given in first argument. Both stdin stream and a
# given file must be sorted the same way.
reject()
{
    diff -u - "$1" | grep '^-' | cut -c2- | sed 1d
}

# Collect lists of words
for YEAR in ????; do
    CENTURY=$((($YEAR - 1) / 100 + 1))
    find "$YEAR" -type f -print0 |
        xargs -0 sed 's/\(.*\)/\L\1/g; s/[^A-Za-z0-9_]/\n/g;' >>words_$CENTURY
done

# Make lists unique and sorted
for C in 19 20 21; do
    sort -u <words_$C >words_unique_$C
done

# Output results
cat words_unique_19 | reject words_unique_20 | reject words_unique_21 >19
cat words_unique_20 | reject words_unique_19 | reject words_unique_21 >20
cat words_unique_21 | reject words_unique_19 | reject words_unique_20 >21

Shell script, 233 bytes
J(){
diff -u - $1|grep ^-|cut -c2-|sed 1d
}
for Y in *; do
C=$(((Y-1)/100-18))
find $Y -type f -exec sed 's/\(.*\)/\L\1/;s/[^A-Za-z0-9_]/\n/g' {} +>>W$C
done
S(){
sort -u
}
S<W0>A
S<W1>B
S<W2>C
J B<A|J C>19
J A<B|J C>20
J A<C|J B>21

Basically a very compressed version of reference solution. Everything that could be replaced with 1-letter name was replaced. Still works in minimal sh.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Constructing an Orthogonal-Diagonal Greco-Latin Square
Consider a grid of NxN unique elements.  Each element has a letter (from A to the Nth letter, inclusive) and a number (from 1 to N, inclusive).  Hence, each number/letter pair is in the grid exactly once.
Your job is to arrange a grid such that:
Each row, column, and diagonal (including wrapping) contains each letter and number exactly once.
By wrapping, I mean that
* * * # *
* * # * *
* # * * *
# * * * *
* * * * #

is a diagonal, along with all similar diagonals that hit the edges.
An example 5x5 grid is:
A1 B2 C3 D4 E5
C4 D5 E1 A2 B3
E2 A3 B4 C5 D1
B5 C1 D2 E3 A4
D3 E4 A5 B1 C2

Your task is to write a program that accepts a number, N, and print a NxN grid as described above. Your program should work for any 0 < N <= 26.  If a particular grid is not possible, then you should print Impossible.
Hardcoding the answer for any N is not allowed. A program is hard coded if it calculates the grid in different manner (as judged by me) for any N > 26 (or if it fails to calculate).  (This is meant to prevent precalculation, including precalculated invalid grids, or offsets for given grids).
This is a fastest-code problem, and your score is the sum of the times taken to run your program across all possible N on my computer.  In your answer, please have your program run across all N (so I only have to time it once).  If no program can compute it in under 60 seconds, then the winner is the answer that can calculate the grid with the largest N in 60 seconds.  If multiple programs have the same maximum N, then the tiebreaker is the fastest solution.
(I have a decently powered Windows 8 machine, and any compilers or interpreters needed must be freely available for it).

The fact that your machine is Windows and not Linux might be bothersome for some technologies.

+1 for the question, but given that analysis of your example seems to give away a pretty fast algorithm, I wonder if you will actually be able to measure the speed. Can we write a function that returns a string? Because I believe the time the API calls take to do the actual printing will be longer than the calculating.

@steveverrill yes, for timing purposes, returning a string is acceptable.

What's the purpose of letters and numbers. Does each number only appear next to each letter once, or can 1 appear always next to A, 2 next to B, ...?

@Jakube yes.  Each element must be unique, meaning that each number/letter pair in the grid must be unique.

@NathanMerrill: You should include that information "that each number-letter pair in the grid must be unique". It is crucial, otherwise it'd just be equivalent with just numbers (keeping the letters aligned with the numbers)

This is more complicated than I thought. The algorithm I was thinking of using (shift the same, carefully chosen number of places on each row) fails for 2,3,4 and 6, but I have proved manually that these are impossible. There are some other cases that it fails for, which I believe may also be impossible, but I haven't proved it yet.

Python 3
letters = []
numbers = []
for n in range(1,27):
    if n%2==0 or n%3==0:
        offsets=False
    else:
        offsets = [x for x in range(0,n,2)]
        offsets.extend([x for x in range(1,n,2)])
    letters.append(chr(96+n))
    numbers.append(n)
    if offsets :
        for y in range(n):
            for x in range(n):
                let=letters[(x+offsets[y])%n]
                num=numbers[(offsets[y]-x)%n]
                print (let+str(num), end= "  " if num<10 else " ")
            print("\n")
    else:
        print("Impossible\n")

How it works?
The naive implementation would be to look through all the possible arrangements of letter and numbers
in an NxN grid and look for one that is also a Orthogonal-Diagonal Latin Square (ODLS)
(and thus, for some it would just have to go through all configurations and return impossible). Such
an  algorithm wouldnt suit this challenge due to absurd time complexity.
So there are three major simplifications and justifications (partial proofs and insights to why it works) to ODLS constructions used in my implementation:
The first is the notion that we only need to generate a valid Diagonal Latin Square (A NxN grid such that each row, column, wrapped-diagonal
contains each element of a set of N distinct elements exactly once) of the first N letters of the alphabet.
If we can construct such a Diagonal Latin Square (DLS) then an ODLS can be constructed
using the DLS with appropriate exchange of elements and flipping. Justification:
Let us first look at an example using the example grid
a1 b2 c3 d4 e5
c4 d5 e1 a2 b3
e2 a3 b4 c5 d1
b5 c1 d2 e3 a4
d3 e4 a5 b1 c2
Every ODLS can be separated into two DLS (by definition), so
we can separate the grid above into two DLS, one containing letters, the other - numbers
a b c d e
c d e a b
e a b c d
b c d e a
d e a b c
and
1 2 3 4 5
4 5 1 2 3
2 3 4 5 1
5 1 2 3 4
3 4 5 1 2
If we transform the number DLS by the mapping 1-->e, 2-->d, 3-->c, 4-->b, 5-->a,
1 2 3 4 5 --> e d c b a
4 5 1 2 3 --> b a e d c
2 3 4 5 1 --> d c b a e
5 1 2 3 4 --> a e d c b
3 4 5 1 2 --> c b a e d
Now if we put the transformed number grid next to the original letter grid,
Original  | Transformed
a b c d e | e d c b a
c d e a b | b a e d c
e a b c d | d c b a e
b c d e a | a e d c b
d e a b c | c b a e d
It can be clearly seen that the number grid is a horizontal flip of
the letter grid withminor letter to number substitutions.
Now this works because flipping guarantees that no two pairs occur more than once,
and each DLS  satisfies the requirements of the ODLS.

The second simplification is the notion that if we found a suitable configuration (SC) of one element (A NxN grid such that each row, column, wrapped-diagonal
contains that element exactly once), then a DLS could be constructed by replacing the element and shifting the SC. Justification:
If "_" is an empty space and "a" the element then a valid SC of a 7x7 grid is
a _ _ _ _ _ _
_ _ a _ _ _ _
_ _ _ _ a _ _
_ _ _ _ _ _ a
_ a _ _ _ _ _
_ _ _ a _ _ _
_ _ _ _ _ a _
or
a _ _ _ _ _ _
_ _ _ a _ _ _
_ _ _ _ _ _ a
_ _ a _ _ _ _
_ _ _ _ _ a _
_ a _ _ _ _ _
_ _ _ _ a _ _
(the second one can actually be obtained from the first one via rotation)
now say we took the second SC, shifted it one unit to the right and
replaced all "a" with "b"
a _ _ _ _ _ _       _ a _ _ _ _ _       _ b _ _ _ _ _
_ _ _ a _ _ _       _ _ _ _ a _ _       _ _ _ _ b _ _
_ _ _ _ _ _ a       a _ _ _ _ _ _       b _ _ _ _ _ _
_ _ a _ _ _ _  -->  _ _ _ a _ _ _  -->  _ _ _ b _ _ _
_ _ _ _ _ a _       _ _ _ _ _ _ a       _ _ _ _ _ _ b
_ a _ _ _ _ _       _ _ a _ _ _ _       _ _ b _ _ _ _
_ _ _ _ a _ _       _ _ _ _ _ a _       _ _ _ _ _ b _
Now if we overlaid the SC of "a" with the SC of "b" we get
a b _ _ _ _ _
_ _ _ a b _ _
b _ _ _ _ _ a
_ _ a b _ _ _
_ _ _ _ _ a b
_ a b _ _ _ _
_ _ _ _ a b _
If we repeated these steps for the other five letters, we would arrive at a DLS
a b c d e f g
e f g a b c d
b c d e f g a
f g a b c d e
c d e f g a b
g a b c d e f
d e f g a b c
This is a DLS, since each SC follows the general requirements of a DLS
and shifting ensured that each element has its own cell.
Another thing to note is that each row contains the string "abcdefg" that is offset
by some cells. This leads to another simplification: we only need to find the
offsets of the string in every row and we are finished.

The last simplification is as follows - all DLS of prime N, except for N=2 or N=3,
can be constructed, and if N can be factored into two numbers whose appropriate
DLS can be constructed, then a DLS of that N can be constructed.
I conjecture that the converse also holds.
(In other words we can only construct an DLS for N that is not divisible by 2 or 3)
Pretty obvious why 2x2 or 3x3 cant be made. For any other prime this can be done
by assigning a each consecutive row a shift that is by two bigger than the previous,
for N=5 and N=7 this looks like (with elements other than "a" ommited)
N=5
a _ _ _ _ offset = 0
_ _ a _ _ offset = 2
_ _ _ _ a offset = 4
_ a _ _ _ offset = 6 = 1 (mod 5)
_ _ _ a _ offset = 8 = 3 (mod 5)
N=7
a _ _ _ _ _ _ offset = 0
_ _ a _ _ _ _ offset = 2
_ _ _ _ a _ _ offset = 4
_ _ _ _ _ _ a offset = 6
_ a _ _ _ _ _ offset = 8 = 1 (mod 7)
_ _ _ a _ _ _ offset = 10 = 3 (mod 7)
_ _ _ _ _ a _ offset = 12 = 5 (mod 7
(Why this works on all prime N (actually all N that are not divisible
by 3 or 2) can probably be proven via some kind of induction but i will
omit that, this is just what my code uses and it works)
Now, the first composite number that is not
divisible by 2 or 3 is 25 (it also occurs in the range our program must test)
Let A denote the DLS of N = 5
a b c d e
d e a b c
b c d e a
e a b c d
c d e a b
Let F be the DLS A where each letter is substituted by the letter five postions after it
a-->f, b-->g etc. So F is
f g h i j
j e f g h
g h i j f
j f g h i
h i j f g
Let K be the DLS a where each letter is substituted by the letter ten postions after it
a-->k, b--> l etc.
Let P be defined likewise (so a-->p, b-->q etc)
Let U be defined likewise (so a-->u, b-->v etc)
Now, since the DLS A could be constructed, then by substituting a --> A, b--> F etc.
we get a DLS of N=5*5 (A has five rows and five columns and each is filled with a
grid of five rows and five columns)
A F K P U
P U A F K
F K P U A
U A F K P
K P U A F
Now since smaller DLS in the big DLS satisfies the
conditions of a DLS and the big one also satisfies the DLS conditions,
then the resulting grid is also a DLS

A picture of what i meant with the smaller - bigger DLS
Now this kind of thing works for all constructible N and can be proven similiarly.

I have a strong sense that the converse (if some N isnt constructible
(2 and 3) then no multiple of that N is constructible) is also true but have a hard time
proving it (test data up to N=30 (took a veeery long time to calculate) confirm it though)

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Two-way Palindromic Closure Generator
Introduction
A palindromic closure of an input string is the shortest palindrome that can be constructed out of the input string where the final palindrome starts with the input string.
For this challenge, we will consider a two-way palindromic closure such that

Left Palindromic Closure of an input string is the shortest palindrome possible that starts with the input string.
Right Palindromic Closure of an input string is the shortest palindrome possible that ends with the input string.
Two-way Palindromic Closure of an input string is the shorter of either of Left or Right Palindromic Closure of the input string.

Task
Your task is simple. Given a string (consisting only of printable ASCII, new lines and white spaces), output the two-way palindromic closure of that string. In case of tie, either of the left or right palindromic closures are valid output.
You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument, and either printing the result to STDOUT (or closest alternative) or returning it as a string.
You can assume that the input will never be an empty string.
Few examples:
<Input>   -> <Output>
"abcdef"  -> "abcdefedcba"  (or "fedcbabcdef")
"abcba"   -> "abcba"
"abcb"    -> "abcba"
"cbca"    -> "acbca"

Initial Idea credit goes to VisualMelon, final idea with help from Martin and Zgarb
The terms palindromic closure, left-pallindromic closure and right-palindromic closure were first used and defined by this paper.

I would like to see a palindromic solution...

@ojdo I thought of adding that as a bonus, but I am pretty sure most of the answers would have just used comments to create the palindrome. If some answer can really be a palindrome too, without relying on comments, I would leave a bounty for that answer!

Pyth, 22 19
hfq_TTsm,+z_d+_dzyz

Try it online.
Explanation
The two-way palindromic closure is either of the form AX or XA, where X is the input string and A is a substring of X. I actually has to be a contiguous substring of X, a prefix for the one form, a suffix for the other form. But I don't care about these defails. A substring (contiguous or not) is all I need in Pyth.
                        Implicit: z = raw_input() // Read a string
                 yz     A list with all substrings (contiguous or not) of z
       m                For each of these substrings d, build
        ,                  a pair of two strings:
         +z_d              ( z + inveres(d) ,
             +_dz            inverse(d) + z )
      s                 Sum (put all created pairs into a list)
 fq_TT                  filter elements T, where inverse(T) == T (Palindrom)
h                          Take the first element

Edit
The old version ordered the the strings after filtering by length .olN.... Just realized, that y returns the substrings ordered by length. So these palindromes are already sorted.

Clip, 40
(sl`f[a=ava}+m[i+v+ixx}Rlxm[i+xvu0ix}Rlx

Example
Documents>java -jar Clip4.jar palindrome.clip
abcb
abcba

Explanation
(sl`                                        .- The shortest                     -.
    f[a=ava}                                .- palindrome                       -.
            +                               .- among the following two sets:    -.
             m[i      }Rlx                  .- For each number up to length(x)  -.
                +                           .- combine                          -.
                 v+ix                       .- the last i chars of x, reversed  -.
                     x                      .- and x.                           -.
                          m[i       }Rlx    .- For each number up to length(x)  -.
                             +              .- combine                          -.
                              x             .- x and                            -.
                               vu0ix        .- the first i chars of x, reversed.-.

CJam, 30 bytes
Was really hoping to see a CJam answer by now.. So here it goes :P
q:Q,{)QW%/(Q+Q@+s}%{,}${_W%=}=

I really hate that {,}$ block in there, but I get an unordered list of possible palindromes due to the generation algorithm I am using.
Code explanation
q:Q,{            }%             "Read the input string, store in Q, take length and";
                                "run the code block that many times";
     )QW%                       "Increment the iteration index and Put reversed Q on stack";
         /                      "Split reversed Q into parts of incremented iteration index";
          (Q+                   "Take out the first part and prepend it to Q";
             Q@+s               "Take the rest of the parts and append them to Q";
                   {,}$         "At this point, we have all possible prepended and appended";
                                "sequences of the input string. Sort them by length";
                       {_W%=}=  "Take the first sequence which is a palindrome";

Try it online here

I really hate that {,}$ block in there too! Just kidding, I have no idea what anything in CJam does.

Python 2, 115 113 109 105 96 bytes
f=lambda x:[x for x in sum([[x[:~i:-1]+x,x+x[i::-1]]for i in range(len(x))],[])if x==x[::-1]][0]

Can hopefully golf down further. Bits possibly worthy of note:

using sum for two list comprehensions in one
constructing terms in sorted order to avoid the need for min (suggested by @Jakube)

The items aren't quite in sorted order, so this fails for strings like a.

Mathematica, 96 bytes
There must be a more elegant way than this...
""<>#&@@SortBy[r=Reverse;#/.{b___,a__/;r@{a}=={a}}:>{b,r@{b,a}}&/@{r@#,#}&@Characters@#,Length]&

This defines an unnamed function which takes a string and returns the result.
The basic idea is to

Split the string into Characters.
Form an array with this list and its reverse.
Use pattern matching to find the right palindromic of each of them:
{b___,a__/;r@{a}=={a}}:>{b,r@{b,a}}

Note that this doesn't actually return a flat list. E.g. for {a,b,c} you'd get
{a,b,{c,b,a}}

Sort the two results by length.
Pick the shorter and join it back into a string with ""<>#&@@.

It outputs abacaba when the input is abac. The correct answer is cabac. I think you should flatten them before sorting by length.

@alephalpha Found a better fix that didn't require changing the code size (and which was actually my intention behind not sorting it).

Brachylog (2), 6 bytes, language postdates challenge
~{↔?a}

Try it online!
As usual for Brachylog, this is a function, not a full program.
Explanation
~{↔?a}
~{   }   Find a value that produces {the input} upon doing the following:
  ↔        reversing it;
   ?       asserting that we still have the same value;
    a      and taking either a prefix, or a suffix.

As far as I know (it's not my language, but it seems unlikely), a wasn't added to Brachylog for this challenge, but it comes in really handy here. We use the "reverse, and assert it hasn't changed" method to assert that the value we find is a palindrome.
As for why this produces the shortest palindrome, Prolog's (and hence Brachylog's) evaluation order is heavily influenced by the first thing it evaluates. In this case, that's a "reverse" command, and (like most list operations) it sets an evaluation order that aims to minimize the size of the resulting list. As that's the same as the size of the output, the program happily ends up minimizing exactly the right thing by chance, meaning that I didn't need to add any explicit hints.

a - Adfix wasn't added for this challenge. I had no available symbol with good mnemonics for prefix and suffix, therefore I merged both into adfix which can take subscripts to select prefixes or suffixes only if needed.

Ruby, 76 + 2 = 78
With command-line flags -pl (the l may not be needed depending on how you're doing input), run
$_=[[$_,r=$_.reverse]*"\0",r+"\0#$_"].min_by{|s|s.sub!(/(.*)\0\1/){$1}.size}

Given a string 'abaa', generates the strings 'cbca0acbc' and 'acbc0cbca', where 0 is the unprintable character with ascii code 0. It then deletes one copy of the longest repeated string framing 0 it finds in each, 'a' in the first and 'cbc' in the second, to get the two closures. It then outputs the shortest result.
The only really weird thing about the golfed code is that it shortens the strings in place while sorting them, which we can get away with because min_by only executes the block once per element being compared (both because it's a Schwartzian transform and because there are only two elements to compare).

Python 3, 107 bytes

f=lambda a:[i for i in[a[:i:-1]*j+a+a[-1-i::-1]*(1-j)for i in range(len(a))for j in(0,1)]if i==i[::-1]][-1]

To test:
>>> print("\n".join(map(f, ["abcdef", "abcba", "abcb", "cbca"])))
abcdefedcba
abcba
abcba
acbca

Haskell, 107 bytes
import Data.List
r=reverse
f s=snd$minimum[(length x,x)|x<-map(s++)(tails$r s)++map(++s)(inits$r s),x==r x]

Test:
*Main> mapM_ (putStrLn.f) ["abcdef", "abcba", "abcb", "cbca"]
abcdefedcba
abcba
abcba
acbca

J, 66 62 bytes
3 :'>({~[:(i.>./)(#%~[-:|.)@>),(<@([,|.@{.~)"#:i.@#"1)y,:|.y'

Quite straightforward. The two tricks I use:
The right palindromic closure is the left palindromic closure of the reversed string.
Finding the length of the string with minimum length and palindromity with the expression min(is_palindrome / length).
   f=.3 :'>({~[:(i.>./)(#%~[-:|.)@>),(<@([,|.@{.~)"#:i.@#"1)y,:|.y'

   f 'lama'
lamal

Try it online here.


text:
Count the number of ones in an unsigned 16-bit integer
Write some statement(s) which will count the number of ones in an unsigned sixteen-bit integer.
For example, if the input is 1337, then the result is 6 because 1337 as a sixteen bit binary number is 0000010100111001, which contains six ones.

Related but not dupe: 1 2

3 4

Tip: just as the some of digits in a number is congruent to the number mod 9, the some of bits equals the number mod 1.

@PyRulez Any number is zero modulo 1.

Hi, you have chosen a wrong answer as accepted answer (by default tie breaker logic of earliest post).

@Thomas I never said it was a helpful tip.

Why is this question attracting close votes AFTER most of the answers have been posted? Close voters please indicate your reason in the comments. If it is the acceptance of es1024's (very clever) 4-byte answer which does not comply with standard loopholes (because it uses a builtin) please state that this is the reason. Otherwise, what is it?

@Thomas Slight correction- any integer is zero modulo 1.

80386 Machine Code, 4 bytes
F3 0F B8 C1

which takes the integer in cx and outputs the count in ax, and is equivalent to:
popcnt ax, cx     ; F3 0F B8 C1

And here is an 11 10 byte solution not using POPCNT:
31 C0 D1 E9 10 E0 85 C9 75 F8

which is equivalent to:
xor ax, ax        ; 31 C0   Set ax to 0
shr cx, 1         ; D1 E9   Shift cx to the right by 1 (cx >> 1)
adc al, ah        ; 10 E0   al += (ah = 0) + (cf = rightmost bit before shifting)
test cx, cx       ; 85 C9   Check if cx == 0
jnz $-6           ; 75 F8   Jump up to shr cx, 1 if not

Is this in 32-bit or 16-bit (either real or protected) mode?

@FUZxxl The assembly provided is for 16-bit, though replacing ax and cx with eax and ecx changes it to 32-bit. The bytecode is the same for either.

@es1024 The byte code is the same if this was compiled in 16-bit mode and the 32-bit version in 32-bit mode.

Isn't popcnt a builtin and thus falling foul of standard loopholes? Still credit for the second solution though.

When you claim the length of the machine code, shouldn't the title be "80386 Machine Code", not "80386 Assembler"?

Damn you beat me to POPCNT by a day!  Why don't I check this site more often...

At start of that what is the value for cx?

85 C9 75 F8 => 41 E2 F9?

Python 2, 17 bytes
bin(s).count('1')

The bin built-in returns the integer converted to a binary string. We then count the 1 digits:
>>> s=1337
>>> bin(s)
'0b10100111001'
>>> bin(s).count('1')
6

J (5 characters)
J has no explicit types. This does the right thing for all integers.
+/@#:

+/ the sum
@ of
#: the base two representation

C,21
for(n=0;x;n++)x&=x-1;

you said "write some statements" (not "a function") so I've assumed the number is supplied in x and the number of 1's is returned in n. If I don't have to initialize n I can save 3 bytes.
This is an adaptation of the famous expression x&x-1 for testing if something is a power of 2 (false if it is, true if it isn't.)
Here it is in action on the number 1337 from the question. Note that subtracting 1 flips the least significant 1 bit and all zeroes to the right.
0000010100111001 & 0000010100111000 = 0000010100111000
0000010100111000 & 0000010100110111 = 0000010100110000
0000010100110000 & 0000010100101111 = 0000010100100000
0000010100100000 & 0000010100011111 = 0000010100000000
0000010100000000 & 0000010011111111 = 0000010000000000
0000010000000000 & 0000001111111111 = 0000000000000000

EDIT: for completeness, here's the naive algorithm, which is one byte longer (and quite a bit slower.)
for(n=0;x;x/=2)n+=x&1;

Ref: https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

@edc65 so as it turns out, I reinvented the wheel. At least I saved 2 bytes by omitting the {}. It's such a simple task I shouldn´t be surprised someone already came up with it.

"First published in 1960", impressive.

Correction to naive algorithm: for(n=0;x;x/=2)n+=x&1;

The naive implmentation for(n=0;x;x/=2)n+=x&1; gives a result which is different from, for(n=0;x;n++)x&=x-1; for negative numbers. Try with x=-7, the results are confusing !

@nmxprime the OP asks for unsigned int. for -7 = 11111111 11111111 11111111 11111001 on my 32 bit compiler, I get 30 for the fast algorithm, which is correct. For the naive algorithm, it iterates through -7, -7/2=-3, -3/2=-1, -1/2=0. That gives an incorrect answer. Changing x/=2 to x>>=1 may give the correct answer on some compilers, but C is undefined as to whether a 1 or a 0 is shifted into the empty bit for >> on negative numbers. Those compilers that shift a 1 in will go into an infinite loop. The workaround is to define x as an unsigned int. Then x=-7 loads (1<<32)-7=4294967289 into x.

Nice, 3 bytes shorter than n=__builtin_popcount(x);

Jelly, 2 bytes
BS

Jelly is a new language written by @Dennis, with J-like syntax.
         implicit: function of command-line arguments
B        Binary digits as list
 S       Sum

Try it here.

What is this BS‽ ;-)

Pyth, 4 bytes
sjQ2

The program takes the number whose hamming weight is to be found on STDIN.

Julia, 29 27 19 bytes
n->sum(digits(n,2))

This creates an anonymous function that accepts a single argument, n. To use it, assign it to something like f=n->... and call it like f(1337).
The digits() function, when called with 2 arguments, returns an array of the digits of the input in the given base. So digits(n, 2) returns the binary digits of n. Take the sum of the array and you have the number of ones in the binary representation of n.

This can be a lot shorter: Julia has a function count_ones

@AndrewPiliser: Thanks for the suggestion, but built-in functions which exactly accomplish the task are considered a standard loophole and are frowned upon when not explicitly disallowed.

R, 24 bytes
sum(intToBits(scan())>0)

scan() reads input from stdin.
intToBits() takes an integer and returns a vector of type raw containing the zeroes and ones of the binary representation of the input.
intToBits(scan())>0 returns a logical vector where each element is TRUE if the corresponding binary vector element is a 1 (since all elements are 0 or 1 and 1 > 0), otherwise FALSE.
In R, you can sum a logical vector to get the number of TRUE elements, so summing the vector of logicals as above gets us what we want.
Note that sum() can't handle raw input directly, hence the workaround using logicals.

Wouldn't sum(intToBits(scan())) be the same?

@Sieg: Unfortunately no since sum() can't take input of type raw, which is what's returned from intToBits().

That is really weird to me.

@Sieg: Yeah, it's weird to me too. Oh well. If every porkchop were perfect, we wouldn't have hotdogs.

And that's the weirdest metaphor ever.

APL (Dyalog Extended), 8 3 bytes
+/⊤

Try it online!
-5 from Adám.
  ⊤ convert to base 2
+/  sum

While this is as good as it gets in Vanilla, Extended has +/⊤

Rust, 15 bytes
u16::count_ones

Try it online!
Rust is better than C because count_ones is shorter than __builtin__popcount :)
Every built-in integer type (unsigned or signed, 8/16/32/64/128 bits) supports this method. Since the challenge specifically asks for unsigned 16 bit integers, we use u16 here. Also, while the method is usually called in the form of some_number.count_ones(), u16::count_ones(some_number) is also a valid syntax for calling the same function.

Vyxal, 2 bytes
b∑

Try it Online!
Vyxal s, 1 byte
b

Try it Online!

CJam, 6 bytes
ri2b:+

ri         "Read the input and convert it to integer";
  2b       "Convert the integer into base 2 format";
    :+     "Sum the digits of base 2 form";

Try it online here

Joe, 4 bytes
/+Ba

This is an anonymous function. Ba gives the binary representation of a number and /+ sums it.
   (/+Ba)13
3
   (/+Ba)500
6

Mathematica, 22 18 bytes
Thanks to alephalpha for reminding me of DigitCount.
DigitCount[#,2,1]&

@alephalpha thanks, but DigitCount takes another parameter :)

ES6 (34 22 21 bytes):
This is a simple recursive function that can be shortened a bit more.
It simply takes a bit and runs itself again:
B=n=>n&&(1&n)+B(n>>1)

Try it on http://www.es6fiddle.net/imt5ilve/ (you need the var because of 'use strict';).
I can't believe I've beaten Fish!!!
The old one:
n=>n.toString(2).split(1).length-1

ES5 (39 bytes):
Both functions can be easily adapted to ES5:
function B(n){return n?(1&n)+B(n>>1):0}

//ungolfed:

function B(number)
{
    if( number > 0 )
    {
        //arguments.callee points to the function itself
        return (number & 1) + arguments.callee( number >> 1 );
    }
    else
    {
        return 0;
    }
}

Old one:
function(n){return n.toString(2).split(1).length-1}

@user1455003 gave me a really great idea, that 'triggered' the smallest one:
function B(n,x){for(x=0;n;n>>=1)x+=n&1;return x}

I've adapted it to ES6 and made it recursive to shorten a lot!

Here's a smaller 'reguar' javascript function. function B(n,x){for(x=0;n;n>>=1)x+=n&1;return x}

@user1455003 Thank you A LOT or your suggestion! I've used it and adapted it to ES6 and shortened a lot. Thank you!

Your welcome!  I like what you did with it. With the recursion regular javascript is down to 39! function B(n){return n?(1&n)+B(n>>1):0}

@user1455003 If you want, you can edit the ES5 part and add the byte count to the golfed version. (I think you win reputation with edits).

@user81655 WOW! It works!!! Thank you a lot! I really knew this could be made shorter

(1&n) => n%2?

Forth, 48 49 bytes
: c ?dup if dup 1- and recurse 1+ then ;
0 1337 c

If an actual function is needed then the second line becomes
: c 0 swap c ;

and you call it by "1337 c". Forth's relatively verbose control words make this a tough one (actually, they make a lot of these tough).
Edit: My previous version did not handle negative numbers correctly.

Ruby, 18 bytes
n.to_s(2).count'1'

n.to_s(2).count ?1 also works, but is the same length

2019 version: n.digits(2).sum / 15 bytes

Python, 72 26 bytes
Thanks to mathcat for -12 -27 -36 bytes through various simplifications!
lambda a:bin(a).count('1')

Well, you said statements...

Hi, this can be reduced to 60 bytes by using tabs than spaces and short if.

Actually, 35 bytes by using count.

Sorry for these comments, but 26 bytes as it is allowed to use a function (unless specified in the challenge)

@mathcat I still have a lot to learn...

Maybe you can look through this post, there are a lot of tips to golf python code there :)

btw you can use lambdas on any challenge if the OP didn't ask for a "full program"

><> (Fish), 24 bytes + 2 = 26
0$11.>~n;
2,:?!^:2%:{+}-

The program just does repeated mod 2, subtract and divide until the input number becomes zero, then prints the sum of the mod 2s.
Test with the -v flag, e.g.
py -3 fish.py ones.fish -v 1337

For a 16bit integer the codepoint input probably not adequate. (The -v flag version still works.)

@randomra Damn, you're right. While Unicode input does work, 16-bit is just a few orders of magnitude out of range...

PHP (38 bytes):
This uses the same aproach as my ES6 answer
<?=count(split(1,decbin($_GET[n])))-1;

This is a full code, you only need to put it in a file and access it over the browser, with the parameter n=<number>.
PHP <4.2 (32 bytes):
This is a little shorter:
<?=count(split(1,decbin($n)))-1;

This only works reliably on PHP<4.2 because the directive register_globals was set to Off by default from PHP4.2 up to PHP5.4 (which was removed by then).
If you create a php.ini file with register_globals=On, this will work.
To use the code, access the file using a browser, with either POST or GET.
@ViniciusMonteiro's suggestion (38/45 bytes):
He gave 2 really good suggestions that have a very interesting use of the function array_sum:
38 bytes:
<?=array_sum(str_split(decbin(1337)));

45 bytes:
<?=array_sum(preg_split('//', decbin(1337)));

This is a really great idea and can be shortened a bit more, to be 36 bytes long:
<?=array_sum(split(1,decbin(1337)));

Or you can use echo array_sum(str_split(decbin(1337))); and you can use too echo array_sum(preg_split('//', decbin(1337)));

@ViniciusMonteiro Thank you a lot for your suggestion. I really loved it! I've added it to the answer.

Gain four bytes using <?=substr_count(decbin(1337),"1"); (34 bytes)

@Cogicero And you can save even more by removing the quotes: <?=substr_count(decbin(1337),1);. That is a total of 32 bytes. Considering that it is a different-enough code, don't you want to post it as your own answer? I surelly will upvote it!

@Cogicero It´s only two bytes shorter if you use parametrization: <?=substr_count(decbin($argv[1]),1); (or $_GET[n]; 36 bytes)

You could save 3 bytes with $argn and -F.

@Titus While that's true, it isn't worth it. This is a burried answer from 2015. Over 2 years ago. Nobody will care about that saving.

C#, 45 bytes
Convert.ToString((ushort)15,2).Sum(b=>b-48);

https://dotnetfiddle.net/kJDgOY

b-48 is even shorter, AFAIK

Correct! :) I'll update.

Japt, 3 bytes (non-competitive)
¢¬x

Try it here.

Man, I never see those dates for some reason.

Haha, Japt is shortest :D BTW, ¢o1 l would work as well. Another interesting approach is -¢¬r-0; ¢¬ splits into array of binary digits, r-0 reduces by subtraction, starting at 0, and - negates the result, making it positive.

As of last night, you can now use ¢¬x.

beeswax, 31 27 bytes
Non-competing answer. Beeswax is newer than this challenge.
This solution uses Brian Kherigan’s way of counting set bits from the “Bit Twiddling Hacks” website.
it just runs through a loop, incrementing the bit count, while iterating through number=number&(number-1) until number = 0.
The solution only goes through the loop as often as there are bits set.
I could shave off 4 bytes by rearranging a few instructions. Both source code and explanation got updated:
pT_
>"p~0+M~p
d~0~@P@&<
{@<

Explanation:
pT_            generate IP, input Integer, redirect
>"             if top lstack value > 0 jump next instruction,
               otherwise continue at next instruction
  p            redirect if top lstack value=0 (see below)
   ~           flip top and 2nd lstack values
    0+         set top lstack value to 0, set top=top+2nd
      M        decrement top lstack value
       ~       flip top and 2nd lstack values
        p      redirect to lower left
        <      redirect to left
       &       top=top&2nd
      @        flip top and 3rd lstack values
    @P         increment top lstack value, flip top and 3rd values
 ~0~           flip top and 2nd values, set top=0, flip top and 2nd again
d              redirect to upper left
>"p~0+M.....   loop back

  p            if top lstack = 0 at " instruction (see above), redirect
  0            set lstack top to zero (irrelevant instruction)
  <            redirect to the left
 @             flip top and 3rd lstack values
{              output top lstack value as integer (bitcount)

Clone my GitHub repository containing the beeswax interpreter, language spec and examples.

05AB1E, 3 bytes
bSO

Try it online!

Factor, 9 bytes
bit-count

Try it online!

Python 3.10+, 13 bytes
int.bit_count
Attempt This Online!

K (ngn/k), 10 7 bytes
{+/2\x}

Try it online!
Thanks @coltim for -3 bytes by suggesting me that I can just take the sum instead of the count of 1s
Cast the integer into base 2, then sum.

Rather than removing the 0s and taking the count, could you just take the sum instead? It would then be straightforward to make it tacit.

BitCycle, 5 bytes
?+
 !

Online Interpreter
Kind of  cheaty, as it inputs in binary and outputs in unary. These are the only two I/O formats this language really can handle, but it's also pretty trivial.

Explanation:
? Take input
+ Send all 0 bits up (deleting them) and all 1 bits down.
! Output all bits that arrive here.

Isn't this 5? I think you forgot the newline

Java, 17 bytes
Works for byte, short, char, and int. Use as a lambda.
Integer::bitCount

Test here
Without using built-ins:
42 bytes
s->{int c=0;for(;s!=0;c++)s&=s-1;return c}

Test here

this is a standard loophole: builtin functions that do exactly what you want are forbidden.

@FUZxxl The OP never forbade standard loopholes

@ColeJohnson Standard loopholes are assumed to be closed by default

@FUZxxl While es1024 is right that the standard loopholes are closed by default, using built-in functions is currently not an accepted loophole at a vote breakdown of +43/-26.

Clip, 6
2 ways:
cb2nx1

This is a straightforward translation of the requirement: the count of ones in the base-2 representation of number.
r+`b2n

Another method, which takes the sum of the digits of the base-2 representation.

Octave, 18
sum(dec2bin(s)-48)

Example:
octave:1> s=1337
s =  1337
octave:2> sum(dec2bin(s)-48)
ans =  6

GML (Game Maker Language), 21 bytes
for(n=0;x;n/=2)n+=x&1

C# 38 bytes
Convert.ToString(X,2).Count(C=>C==49);

@Vincent McNabb has suggested a golf which saves one byte (replacing '1' with 49)

Clojure, 42 bytes
#(count(filter #{\1}(Long/toString % 2)))

Reading right to left, convert to a binary string, convert to a sequence of characters, filter on 1s and count how many you have.
EDITED
With help from Sieg

42: #(count(filter #{\1}(Integer/toString% 2)))

You need one more character #(count(filter #{\1}(Integer/toString % 2)))

No you don't. :)

This is what I got when I tried it: CompilerException java.lang.IllegalArgumentException: No matching method: toString_PERCENT_

I tested it in Try Clojure. Apparently the page suddenly doesn't recognize Integer/toString. It worked a second ago though.

Try Clojure works now.  However your sample fails with the Clojure 1.6.0 REPL.

Add the space then.

Perl, 21
$r=grep$v&1<<$_,0..15

PowerShell (51 bytes)
"$([char[]][convert]::ToString($s,2)|%{"+$_"})"|iex

Explanation:
[convert]::ToString($s,2) produces a binary string representation from $s.
[char[]] casts it as a char array and allows us to enumerate each char.
|%{"+$_"} prepends each character with a + sign
"$()" implicitly calls .ToString() on the resulting sub expression
|iex sums the piped string (ie. "+1 +0 +1 +1 +0 +1 +0 +0" = 4)

Hiya! Following the same logic you have, why not use the inline -join operator and an implicit .ToString() to achieve 45 bytes with [char[]][convert]::ToString($s,2)-join'+'|iex ... OR, as a different approach use inline -replace operator to achieve 43 bytes with ([convert]::ToString($s,2)-replace0).length

Haskell 42 chars
t 0=[]
t n=t(quot n 2)++[rem n 2]
f=sum.t

declares the function f :: Integer -> Integer
use from the interactive interpreter as f <number> or add the line main=print$f <number> to the end of the file.

You can save a lot of bytes by directly summing the rem n 2s instead of building a list of it and by using div instead of quot: t 0=0 t n=t(div n 2)+rem n 2 - no f anymore.

Matlab, 13 bytes
de2bi creates a vector of zeros and ones representing the binary number, and sum just returns the sum of all the entries.
sum(de2bi(n))

, 4 chars / 11 bytes (non-competitive)
⨭⟦ïⓑ

Try it here (Firefox only).
Explanation
Converts input to binary, splits along chars, and gets sum of resulting array.

Pyt, 1 byte
Hooray for built-ins.
Ħ

Try it online!
Non-built-in:
Pyt, 3 bytes
ɓƖŚ

Try it online!
Explanation:
      Implicit input
ɓ     Convert to binary string
Ɩ     Cast as integer
Ś     Sum of digits
      Implicit output

Brachylog, 2 bytes
ḃ+

Try it online!
Just about exactly the Jelly answer.

><>, 18 bytes
0$:2%:{+}-2,:@?!n!

Try it online!

MathGolf, 2 bytes
âΣ

Try it online!
Explanation
â    convert to binary
 Σ   sum(list), digit sum(int)

Completely unrelated to this answer of yours, but I'm unable to find the MathGolf chat anymore.. Is there an infinite loop or infinite list in MathGolf?

I've been stressed out with school and work for the past few months, so the chat must be inactive. There's no implicit infinite loop, but if you can make sure that the top of the stack evaluates to true you could use the do-while-without-pop. Once I feel that I have time to answer questions on a regular basis, I'll ask to have the chat reopened. Right now I'm just building a todo-list of features I want to add.

I'm getting "Not yet implemented" ValueErrors for all while / do-while loops.. :S Unless I'm doing something wrong..

you should use them like {1}∟ or using the fixed size blocks. It's on my todo-list to have the loop operators also close the block, but it's not implemented as of now.

@KevinCruijssen just as a side note, you're very welcome to ask questions related to MathGolf like this, I'll answer when I find the time. My goal is to set aside more time for the MathGolf chat, but right now it'll remain closed.

In that case a few questions. :) Is only 1 truthy in MathGolf (like in 05AB1E), or is 0/""/[] falsey and (almost) everything else truthy (like in Python)? And let's say I want an infinite loop printing numbers 1,2,3,... every time on a new line. I would expect something like Ä1∟îp would work, but apparently it does not. What should it be instead?

@KevinCruijssen Maybe I need to clarify the loop structure a bit better, but the correct implementation would be something like {îo}▲. Your script first does Ä1∟ which will push 1 onto the stack until the memory is full or TIO timeouts, then it would print the length of the loop. Basically, in pseudo code it would be int i = 0; do {i++; stack.push(1);} while (i != 0); print(i). The code would never reach the last part since the loop is infinite. Basically, loops are constructed as {<loop code>}<loop operator>

Let us continue this discussion in chat.

K (ngn/k), 4 bytes
+/2\

Try it online!
Convert to base 2, sum up.

JavaScript, 19 bytes
f=n=>n&&n%2+f(n>>1)

Try it online!
Nice and simple

Desmos, 40 38 bytes
f(x)=floor(mod(x/2^{[0...x]},2)).total

Try it on Desmos!
-2 bytes thanks to emanresu A

Not sure how to golf this but something like https://www.desmos.com/calculator/chncunsuhu might be shorter?

@emanresuA thanks that's one byte less and two bytes less with dot notation for total

Zsh, 27 bytes
a=${$(([##2]$1))//0};<<<$#a

Try it online!
 30b
 35b

$(([##2]$1)) convert input $1 to binary
${ ... //0} remove 0s
<<<$#a print length of string $a

K5, 9 bytes
+/(16#2)\

I used k5's "unpack" overload for \ to split the number into base 2 digits. You can try it online here using oK.

Go, 24
This is an adaptation of the C solution by @steveverrill
n:=0;for;x>0;n++{x&=x-1}

We need to explicitly declare n outside the loop to keep it in scope.
Go requires curly braces as well, and the check in the for loop must be a boolean expression.
http://play.golang.org/p/Z_iuGL5nZ5

WDC 65816, 8 bytes
Assuming 8-bit XY (P.x = 1), the following 8 bytes of object code produce the popcnt of A in X within 145 cycles:
A2 00 4A 90 01 E8 D0 FA

This works on a 65816 whether A is 8-bit (P.m = 1) or 16-bit (P.m = 0), and it has also been tested in a virtual 6502 with 8-bit values. With 16-bit XY on a 65816 (P.x = 0), one more byte is needed: replace A2 00 with A2 00 00.
Assembly source:
  ldx #0       ; A2 00, or A2 00 00 in 16-bit XY mode
loop:
  lsr a        ; 4A    Copy bit 0 of A to carry and shift A right by 1
  bcc zerobit  ; 90 01 If carry is 1, add 1 to X
  inx          ; E8
zerobit:
  bne loop     ; D0 FA If the last ALU result was nonzero, keep counting

The bne instruction branches on the zero flag, which changes whenever an instruction writes to register A, X, or Y. For a 1 bit, inx is the last instruction to write to A, X, or Y, and X is nonzero if there are 1 to 255 bits (only 16 are possible!), so the loop continues. For a 0 bit, lsr a is the last instruction to write to A, X, or Y, and A is nonzero only if there are more bits to count.

perl (35 characters)
$b=sprintf("%b",$d);$c=()=$b=~/1/g;

Clip, 22 chars (25 for full program, or 27 for working with zero)
[Fy?!%lyWOO])Fmy#WilyW

Prefix this with F<some value> to get the answer for that value. Or, for a full program to read from stdin, prefix the code with Fnx. In a previous answer, I golfed a way in Clip to check if something's a power of two. I always return one in that case. Otherwise, increment the result of applying this function (recursively) to 2^(floor(log2(<function parameter>))).
To make this work with zero (returning 0), use (28 chars):
[Fy?!yZ]?!%lyWOO])Fmy#WilyW

Bash, 63 51 47 bytes
[ $1 = 0 ]&&echo 0||echo $[$1%2+`$0 $[$1/2]`]

The shorter the code, the clearer the meaning :).

51:
[ $1 -ne 0 ]&&echo $[($1&1)+$($0 $[$1/2])]||echo 0

Recursive script instead of script with recursing function.

The "negative-cond || instruction" idiom instead of boring
"if cond; then instruction; fi " is our friend here.
Note that echo should return 0 (true), so [ $1 -ne 0 ] && echo $[$[$1&1]+$(n $[$1/2])]
has the logical value of [ $1 -ne 0 ] alone.

Perl 6: 17
The first thing that comes to mind is
[+] 1337.base(2).comb; # returns 6

Although this doesn't have any arbitrary limits ( the only limits are how much memory you have, and how long you are willing to wait )
[+] ( uint64.Range.max * 2 + 1 ).base(2).comb; # returns 65

# 340282366920938463463374607431768211455
my $uint128-max = :2( 1 x 128 );
[+] $uint128-max.base(2).comb; # returns 128

my $uint8192-max = :2( 1 x 8192 ); # 2467 digit Int
[+] $uint8192-max.base(2).comb; # returns 8192 (takes about a second currently)

Without making it into a Callable the shortest way to write this is to put the Int into the "default" variable $_. ( .method is always short for $_.method )
$_ = 1337;
[+] .base(2).comb;

given 1337 { # Perl6's with/switch statement
  [+] .base(2).comb
}

[+] .base(2).comb given 1337; # ditto

if 1337 -> $_ { # pointy block
  [+] .base(2).comb
}

If you want to create a Callable you could just put it into a Block.
my $code-ref = {[+] .base(2).comb};
# if it is called with an argument it places it in $_
# if called without an argument uses the $_ from an outer scope

If you really want to call it as a normal subroutine:
my &f={[+] .base(2).comb}; # sub f($_){[+] .base(2).comb}

say f 1337; # 6

$_ = 1337;
say f; # 6

Based on your requirements I'd guess that the answer you are looking for is:
[+] .base(2).comb

This assumes that the value is already in $_. It would most likely be the last statement in a subroutine, the right side of an assignment, or an argument to a subroutine or method. ( Otherwise it calculates the result only to throw it away, unless the compiler notices that the result is unused )

In case you were wondering [+] 1, 2, 3 can be considered short for (1,2,3).reduce(&[+]).
Where &[+] is short for &infix:< + > the collection of multi subs available in the current scope that are responsible for the numerical infix addition operator +.

ActionScript 3, 17 bytes
for(;x;n++)x&=x-1

This is a copy of steveverrill answer, how ever by using AS3, I don't have to put ; at the end of the line, so I save 1 byte.
Also I assume that x and n been initialize already.

O, 7 bytes
H2b~]+o
Explanation:

H        Push input into array
  2b~    Push all the bits of the binary form to the array
     ]+o Add them all up and output the array

TeaScript, 9 bytes (non-competitive)
x÷f»l¦1)n

Try it here.

Seriously, 6 bytes (non-competitive)
This one is fun and neat, and given the number of non-competitive entries it has attracted, I might as well add a Seriously answer.
'12,¡c

Try it online
Explanation:
'12,¡c
   ,     get input
  2 ¡    convert to binary string
'1   c   count the occurrences of "1"
         (implicit print at EOF)

Candy, 15 bytes
I would have thought this would do a bit better, but the lack of an operator to convert numbers to a base 2 string seems to have hurt it.  Maybe in a future version of Candy to pull an int from the stack and push 1's and 0's.  That would make this one kind of boring, just XS?.
(~A2%h2/LD{)|=Z

The long form is:
while   # stack not empty
  peekA
  pushA
  digit2
  mod       # get low bit
  popAddZ   # Z = Z + low bit
  digit2
  div
  floor     # integer div 2
  dupl
  if        # if the top of stack is non-zero
endwhile    # NOTE that the endwhile is in an if-then clause
  else
    popA
    pushZ   # NOTE the lack of an endif.
            #  braces and parens are calculated as the
            #  program counter advances over them

C# 45
int o=Convert.ToString(n,2).Count(x=>x=='1');

where o holds the amount of ones and where n is the number.
Alternative and faster
C# 6.0 88 bytes
int o=b(n,16).Count(x=>x=='1');
static string b(int v,int l)=>(l>1?b(v>>1,l-1):null)+"01"[v&1];

where the o holds the number of ones and where the n is the number.

Javascript ES6, 35 bytes
a=>a.toString(2).match(/1/g).length

x86 cpu instructions, 30 bytes
56 89 E6 8B 44 04 3D 00 00 74 0F D1 E8 50 E8 EF FF 8B 4C 04 81 E1 01 00 01 C8 5E C2 02 00

meaning and disassembly:
; input in the stack sp+4
; output in ax
;0i,2Ka,4P
f:
push  si
mov   si,  sp
mov   ax,  [si+4]
cmp   ax,  0
je   .z
shr   ax,  1
push  ax
call  f
mov   cx,  [si+4]
and   cx,  1
add   ax,  cx
.z:
pop   si
ret 2

0000000F  56                push si
00000010  89E6              mov si,sp
00000012  8B4404            mov ax,[si+0x4]
00000015  3D0000            cmp ax,0x0
00000018  740F              jz 0x29
0000001A  D1E8              shr ax,1
0000001C  50                push ax
0000001D  E8EFFF            call 0xf
00000020  8B4C04            mov cx,[si+0x4]
00000023  81E10100          and cx,0x1
00000027  01C8              add ax,cx
00000029  5E                pop si
0000002A  C20200            ret 0x2
//30

RProgN, 8 Bytes
2 B S ++

Explination
2 B     # Convert to base 2
S       # Convert from string to a stack of individual characters
++      # Sum the stack.

Simple enough, Could be made cheaper if the sugar for sum was single character, instead of double, as ►2BS<SUM> could then be used, saving a byte.
Test Cases
1337:       6.0
16:         1.0
255:        8.0
1236172031: 21.0

16/32-bit x86 assembly, 9 bytes
(based on es1024's answer)
31 C0 D1 E9 10 E0 41 E2 F9
which is equivalent to:
xor ax, ax        ; 31 C0   Set ax to 0
shr cx, 1         ; D1 E9   Shift cx to the right by 1 (cx >> 1)
adc al, ah        ; 10 E0   al += (ah = 0) + (cf = rightmost bit before shifting)
inc cx            ; 41      Increment cx to offset following decrement
loop $-5          ; 75 F9   Jump up to shr cx, 1 if cx-1 is not zero
cx is the 16-bit integer to profile, result is returned in ax.

Pip, 5 bytes
(The language postdates the question, barely.)
1NTBa

Try it online!
With the knowledge that a represents the first command-line argument, this program can be understood quite straightforwardly: 1 iN To-Binary(a). That is, convert a to binary and count the number of 1s.

Stax, 4 bytes
:B|+

Run and debug online!
Explanation
:B|+
:B      Binary digits
  |+    Sum

Japt -x, 3 2 bytes
ì2

Try it here

dc, 25 bytes
[2~rd0<B]dsBx[+z1<S]dsSxp

Try it online!
Two macros.
[2~rd0<B]dsBx breaks a decimal value down into binary components by repeatedly dividing by two (using ~ to leave both quotient and remainder on stack) until left with a quotient of zero. After our stack is filled with ones and zeros, [+z1<S]dsSx sums it up by adding the top two values until there's only one value left. p prints our final answer.

Add++, 8 bytes
L,BBBDBs

Try it online!
Surprisingly short for Add++
How it works
L,      ; Define a lambda function
        ; Example argument: 1337
    BB  ; Binary;  STACK = [10100111001]
    BD  ; Digits;  STACK = [[1 0 1 0 0 1 1 1 0 0 1]]
    Bs  ; Sum;     STACK = [6]

Kotlin, 30 bytes
{it.toString(2).sumBy{it-'0'}}

Try it online!

cQuents, 6 bytes
uJ$);1

Try it online!
Explanation
:uJ$);1
:            implicit :
              mode: sequence 1 - given input n, output nth term in sequence
             each term in the sequence is

 u   ;1      count(                , 1)
  J )              toBase(     , 2)
   $                      index

PARI/GP, 13 bytes
hammingweight
Attempt This Online!
PARI/GP has a built-in for this.

PARI/GP, 17 bytes
n->sumdigits(n,2)
Attempt This Online!
Another built-in, with a more obvious name.

PARI/GP, 21 bytes
f(n)=if(n,n%2+f(n\2))
Attempt This Online!
Without built-in.

Perl 6, 18 bytes
*.base(2).comb.sum

Works with any nonnegative integer, in fact.
Try it online!

8051 Machine Code, 13 bytes
7B 10 E8 13 50 01 0A BB 08 01 E9 DB F6

Takes the integer in R1 (highest 8 bits) and R0 (lowest 8 bits). Returns the result in R2
    MOV R3, #10        ; 7B 10     - Store 16 since we process a 16 bit number
    MOV A, R0          ; E8        - Move the first register to check to A

LAB1:
    RRC A              ; 13        - Rotate A through the carry to extract the nth bit
    JNC LAB2           ; 50 01     - If the current bit is set (Carry = 1)
    INC R2             ; 0A        - Increment the result

LAB2:
    CJNE R3, #08, LAB3 ; BB 08 01  - If we are done with the first 8 bits
    MOV A, R1          ; E9        - Move R1 into the accumulator

LAB3:
    DJNZ R3, LAB1      ; DB F6     - Jump back to LOOP if we have done less than 16 iterations
END

SMALL, 28 bytes
0->n{x?[x%2=1?n+1->n]x/2->x}

Takes input in variable x and the output will be in variable n.
{
  x?

  [
    x % 2 = 1?
    n + 1 -> n
  ]

  x / 2 -> x
}

Repeatedly divides x by two until the number is zero, which means every 1 bit will be moved into its rightmost bit at some point. We then perform a check each loop to see if this bit is a 1 and if so, increment n.

Thunno 2 S, 2 bytes
2B

Attempt This Online!
Convert to a binary list. S flag takes the sum.
Thunno 2, 3 bytes
ḃ1c

Attempt This Online!
Convert to binary and count the 1s.

LUA 55 bytes
while(i>0)do if(v-i)>=0 then c=c+1;v=v-i;end i=i/2 end

v    is the value
i    is the max value of an (x)bit Integer, 65535 in this example.
c    counts one up, if there's a remainder from (i-l), which means that a one is found.

This is more a simple algorithm than a single statement.

Not valid, c is not declared, and will error when (c=c+1) happens, you cannot assume i is a value, and you cannot assume the input is v.
Please use the standard io methods.

Uhm,.. what? You can declare by defining in lua.

The declaring of these things must be part of the code.

EG,
i=65535 c=0 v = io.read() while(i>0)do if(v-i)>=0 then c=c+1;v=v-i;end i=i/2 end

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Determine sets of associatively equivalent permutations of commutative operations
There are many types of binary operations, which can be categorized by their associative properties and their commutative properties.

A binary operation () is associative if the order of operations between operands does not affect the result — i.e. if (a(bc)) = ((ab)c).
A binary operation () is commutative if the order of two operands within one operation does not affect the result — i.e. if (ab) = (ba).

There are operations like addition and multiplication that are both associative and commutative, and operations like subtraction and division that are neither associative nor commutative.
There are also operations — such as the group composition operator — that are associative but not commutative.
But then there are operations that are commutative but not associative. These are more rare and not analyzed as much mathematically, but they occur. For example, rounded multiplication is such an operation. If you round a calculation to the nearest tenth after every multiplication, you can get anomalies like (6.8 × 5.7) × 2.9 = 112.5 while 6.8 × (5.7 × 2.9) = 112.2.

Let a permutation of the operands P in an operation tree (such as ((x(xx))((x(xx))x))) be associatively equivalent to another permutation Q, if the operands in P can be rearranged by the commutative property to form an operation tree identical to the original.
For example, permutations (a(b(c(de)))) and (a(b(c(ed)))) of the operation tree (x(x(x(xx)))) are equivalent, because d commutes with e. However, (a(b(c(de)))) and (a(b(d(ce)))) are not equivalent, because (c(de)) is not equal to (d(ce)).
A more complex example might be (((ab)c)(d(ef))) and (((ef)d)(c(ba))). Step-by-step, the two of these can be shown to be equivalent as follows:
(((ab)c)(d(ef))) = (((ba)c)(d(ef)))     since    a    commutes with    b
(((ba)c)(d(ef))) = (((ba)c)((ef)d))     since  (ef)   commutes with    d
(((ba)c)((ef)d)) = ((c(ba))((ef)d))     since  (ba)   commutes with    c
((c(ba))((ef)d)) = (((ef)d)(c(ba)))     since (c(ba)) commutes with ((ef)d)

Permutations of different operation trees are not comparable. (a(b(c(de)))) and ((((ab)c)d)e) are neither associatively equivalent nor associatively distinct, because their operation trees are different.

Your task is to build a program that will find all the associatively equivalent permutations of the operands of a given operation tree.
Your program will take input in the form given above, with brackets enclosing juxtaposed operators. The operands will always be lowercase letters, in alphabetical order starting from a, and will contain a maximum of 26 letters.
Your program will output a series of permutations of the letters, without the brackets, representing all of the permutations that are associatively equivalent with the original permutation.
For example, if you are given an input of:
((ab)(cd))

Then your program will output:
abcd
abdc
bacd
badc
cdab
cdba
dcab
dcba

Your program must be accompanied by a description of its algorithm, and a proof of its asymptotic runtime with respect to the number of operands in the operation tree. The program with the lowest asymptotic runtime in this manner wins.

With all of those parentheses everywhere, I thought I was looking at Lisp code.

Note: I have no idea whether this problem is NP-hard or not; I just thought of it.

Why are you calling this equivalence relation associatively equivalent? Shouldn't it be commutatively equivalent?

@JoeZ. The output size can be O(2^input_size) e.g. with a full binary tree. I'm not sure if that proves NP-hardness but it proves O(2^input_size) running time.

@PeterTaylor Because each set of these permutations forms an equivalence class of operand permutations that are equivalent without associations being universal.

@randomra Maybe I should have made the problem about printing out the equivalence classes instead.

Every parenthesis has in it two elements, either a terminal symbol, or another parenthesis. These two elements have two possible permutations, ab and ba.
This means that the expression forms a binary tree, and every node inside the tree has two possible permutations. So the total output is always 2n where n is the number of parenthesis pairs. This means that an asymptotical algorithm will always do this amount of work.
For this optimal algorithm we will parse the expression, then recursively generate possibilities, 2 for each parenthesis pair. As seen in the paragraph above, this is optimal.
def parse(inp):
    c = inp.pop(0)
    while c == ")": c = inp.pop(0)

    if c == "(":
        return [parse(inp), parse(inp)]

    return c

def possibs(tree):
    if len(tree) == 2:
        for left_possib in possibs(tree[0]):
            for right_possib in possibs(tree[1]):
                yield left_possib + right_possib
                yield right_possib + left_possib
    else:
        yield tree

tree = parse(list("((ab)(cd))"))

for possib in possibs(tree):
    print(possib)

The expression only has 2^n permutations when the operation tree is full. For something like ((a(bc))d) you get trees such as (d(a(bc))) which are not associatively equivalent.


text:
Make the function comparing two variables with different value print True
Without changing the actual function, call it in such a way that it prints "True"
void Puzzle(out int x, out int y)
{
  x = 0;
  y = 1;
  Console.WriteLine(x == y);
}

Online Tester

Programming puzzle challenges should usually include some indication how the "best" answer is chosen is several valid solutions are posted.

Reusing reference:
//C# Puzzle: Call the Puzzle() function in Main such that it prints True.
//You have to do this without changing the Puzzle method.

public void Main()
{
  int x,y;
  Puzzle(out x, out x);
}

void Puzzle(out int x, out int y)
{
    x = 0;
    y = 1;
    Console.WriteLine (x == y);
}

Solved!
Puzzle(out x, out x);

http://volatileread.com/utilitylibrary/snippetcompiler?id=9697