How many $6$ digit numbers there are, where first and last digits and also consecutive digits are not equal? We have a 6 digit number
$a_1a_2a_3a_4a_5a_6$ and $a_1 \neq 0$
also $a_1 \neq a_2, a_2 \neq a_3, a_3 \neq a_4, a_4 \neq a_5, a_5 \neq a_6, a_6 \neq a_1$
All of numbers where $a_1 \neq a_2, a_2 \neq a_3, a_3 \neq a_4, a_4 \neq a_5, a_5 \neq a_6$ are $9^6$
I'm having troubles with the last case.I know that this is generalization of $a_1a_2a_3$ for which there are $8*9^2$ numbers but cannot figure out how they are related
and this is the source file which counts all those digits.
bool foo(int num)
{
    char str[15] = {};
    int i=0;
    while(num)
    {
        str[i]=num%10;
        num/=10;
        i++;
    }
    str[i]=str[0];
     for(int j=0;j<i;j++)
            if(str[j]==str[j+1])
                return false;
    return true;
}

int main()
{
    int sum=0;
    for(int i=100000;i<=999999;i++)
        if(foo(i))
            sum++;
    cout<<sum;
    return 0;
}

Please note that this program produces answer: 478305, which is correct
Also note that the answer 8*9^5 misses some cases
 A: Let $f(n)$ denote the number of strings $a_1\cdots a_n$, where no consecutive digits are equal, and $a_1\ne a_n$.  Let $g(n)$ be the number of strings where no consecutive digits are equal, but $a_1 = a_n$.  The OP notes that $f(n)+g(n)=9^n$.
We'll write down a recurrence involving both $f$ and $g$, and solve for $f$.  It's easy to see that $f(1)=9$, $f(2)=9^2$, $f(3)=8\cdot 9^2$.  So suppose $n\ge 4$; to compute $g(n)$, we assume $a_n=a_1$.  We have $9$ choices for each of $a_1,\ldots, a_{n-2}$.  The number of choices for $a_{n-1}$ depends on whether $a_{n-2} = a_n$ or not.  If so, there are $9$ choices, and there are $g(n-2)$ ways for this to happen.  If not, there are only $8$ choices for $a_{n-1}$, and there are $f(n-2)$ ways for this to happen.
This gives the recurrence $g(n)=9 g(n-2) + 8 f(n-2)$.  Substituting $g(n)=9^n-f(n)$ we see
$$ f(n) = 8\cdot 9^{n-1} + f(n-2),\,n\ge 4.$$
We conclude $f(6)= 8\cdot 9^5 + 8\cdot 9^3 + 9^2 = 478305.$
A: WRONG ANSWER (for reason noted below)
a1 can be any one of 9 numbers, (1,2,...,9)
a2 can be any one of 9 numbers, (0,1,...,9 not a1)
.
.
.
a6 can be any one of 8 numbers, (0,1,...,9 not a5 and not a1)

These choices are all unique and exhaustive.  So I get 9^5 * 8.
CORRECTION: Saying that a6 can be any one of 8 numbers, (0,1,...,9 not a5 and not a1) IS WRONG if a5=a1.  In that case, a6 can be any one of 9 numbers.
A: Here's another approach.  We will do cases based on the digits in positions $1$, $3$, and $5$.
Case 1: 
$a$, ___ , $a$, ____, $a$, ____.  
There are $9$ ways to select the digit $a$, and $9$ ways to fill each blank. So  $9^4$ numbers of interest in this case.
Case 2.1, 2.2, 2.3:  
$a$, ___ , $a$, ____, $b$, ____ 
and $a$, ___ , $b$, ____, $b$, ____ 
and $b$, ___ , $a$, ____, $a$, ____
For each of three subcases, there are $9\cdot 9$ ways to choose $a$ and $b$, and $9\cdot 8\cdot 8$ ways to fill the blanks.  So there are a total of $3\cdot 9^3\cdot 8^2$ numbers of interest in these three subcases combined.
Case 3:  
$a$, ___ , $b$, ____, $c$, ____.  
There are $9\cdot 9\cdot 8$ ways to choose $a, b,c$, and $8$ ways to fill each blank.  So there are a total of $9^2\cdot 8^4$ numbers of interest in this case.
Grand total: $9^4+3\cdot 9^3\cdot 8^2+9^2\cdot8^4=478305$ numbers of interest.
A: You need to examine each position - whether it is the same as $a_1$, or not. Although this is slow in general, it's OK with a few cases, like here for n=6. So here we go, I denote different choices with different letters:
1. $a_1 = A$ - 9 choices. | A | _ | _ | _ | _ | _ |
2. $a_2 = B$ - 9 choices. | A | B | _ | _ | _ | _ |
3.A. $a_3 = a_1 = A$ - 1 choice. Then $a_4 = D$ - 9 choices. | A | B | A | D | _ | _ |


*

*3.A.4.A. $a_5 = a_1 = A$ - 1 choice, then $a_6$ - 9 choices - in total $\fbox{$9^4$}$ | A | B | A | D | A | F |

*3.A.4.B $a_5 = E \ne a_1$ - 8 choices, then $a_6$ has 8 choices
- in total $\fbox{$9^3.8^2$}$ | A | B | A | D | E | F |

3.B. $a_3 = C \ne a_1$ - 8 choices | A | B | C | _ | _ | _ |


*

*3.B.4.A. $a_4 = A$ - 1 choice => $a_5 = E\ne A$ - 9 choices => $a_6 = F$ - 8 choices
- in total $\fbox{$9^3.8^2$}$ | A | B | C | A | E | F |



*

*3.B.4.B. $a_4 = D\ne a_1$ - 8 choices | A | B | C | D | _ | _ |


*

*3.B.4.B.5.A. $a_5 = a_1 = A$ - 1 choice => $a_6 = F$ - 9 choices
- in total $\fbox{$9^3.8^2$}$ | A | B | C | D | A | F |

*3.B.4.B.5.B $a_5 = E\ne a_1$ - 8 choices => $a_6 = F$ - 8 choices
- in total $\fbox{$9^2.8^4$}$ | A | B | C | D | E | F |

And now, just sum up the results: $3.9^3.8^2+9^4+9^2.8^4 = $478305, exactly what we needed.
Tad's response is also great and timely!
