Light bulbs math problem

how many prime factors there are
u have to count prime factors, which occur double only once
but u have to consider the products of the prime factors

e.g:

2*2*3*5=60
it flips with 2,3,5,
4=2*2, 2*3=6, 2*5=10,
2*2*3=12, 2*2*5=20, 2*3*5=30
and 2*2*3*5=60

so there are 10 flips -> light on

Well, the only lights that are going to be on are the ones that have an odd number of factors. The only way a number has an odd number of factors is if it is a square number. Eg. Factors of 4 = 1,2,4; Factors of 36 = 1,2,3,4,6,9,12,18,26

This means the bulbs that will be on will be
1^2 = 1
2^2 = 4
3^2 = 9
4^2 = 16
5^2 = 25
6^2 = 36
7^2 = 49
8^2 = 64
9^2 = 81
10^2 = 100

For the case of n bulbs, there will be floor(sqrt(n)) bulbs lit.

my guess:

as Slithe said, a light bulb is left on if and only if it has an odd number of factors.

I claim that every number other than a perfect square has an even number of factors.

Say you're given a number n. For every factor f there exists another factor n/f. So for each factors come in pairs. To illustrate this, consider 12 (with factors 1, 2, 3, 4, 6, 12 and factors "pairs" 1*12, 2*6, 3*4).

However, if you have a perfect square, one of the "pairs" reduces to a singlet because the "pair" consists of only one unique number. Consider 9 (with factors 1, 3, 9 and "pairs" 1*9, 3*3).

Thus, only the square of an integer will be left on after everyone flips a switch.

Now, if given a general n, exactly [[sqrt(n)]] - 1 light bulbs will be left on, since the number of perfect squares less than n is exactly the greatest integer less than sqrt(n). Consider n = 10 with 1, 4, and 9 perfect squares less than n and sqrt(10)=3.16227766.

So when n = 100, sqrt(100) = 10 light bulbs will be lit. Namely, #'s 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100.

Primefactor n=P1^e1*...*Pr^er
number of factors=(e1+1)(e2+1).....(er+1)=odd <=> each factor odd <=> 2|ei for all i <=> n is square

1
4
9
16
25
36
49
64
81
100

This problem is all about number of factors.

If a number had an even number of factors (counting 1 and the number itself, not that it matters since they form a pair), then it will be off, otherwise it will be on.

Now, in order to get this number, all factors need to be paired, unless it is a perfect square, in which case, the factor pair will be the same number, and we can count it only once.

As a result, only perfect squares have odd number of factors.

You can compile it using snippet compiler (which is awesome)

using System;
using System.Collections.Generic;

public class MyClass
{
public static void Main()
{
int[] lightbulb;
lightbulb = new int[101];

for( int i = 0; i < 101; i ++ )
{
lightbulb[i] = 0;
}
for( int j = 1; j < 101; j++ ) // people
{
for( int i = j; i < 101; i+=j ) // lightbulbs
{
lightbulb[i] ++;
if( lightbulb[i] ==2 )
{
lightbulb[i]=0;
}
if( i == 2 )
Console.WriteLine( "j=" + j +", i=" + i +"\t" + lightbulb[i]);
}
}
List<int> on = new List<int>();
for( int i = 0; i < 101; i ++)
{
if( lightbulb[i] == 1 )
{
on.Add( i );
}
}
foreach( int temp in on )
{
Console.WriteLine( temp );
}
RL();
}

#region Helper methods

private static void WL(object text, params object[] args)
{
Console.WriteLine(text.ToString(), args);
}

private static void RL()
{
Console.ReadLine();
}

private static void Break()
{
System.Diagnostics.Debugger.Break();
}

#endregion
}

They'll all be off?